Description
给定一个序列，选择其中 (m) 个数，记下标为 (b) 序列，最大化
[sum_{i=1}^m ma_{b_i}-sum_{i=1}^m sum_{j=1}^m f(min (b_i,b_j),max (b_i,b_j))
]
其中 (f(i,j)) 表示序列 (a) 区间 ([i,j]) 的最小值。
Solution
首先应该观察到第一个和式里带了一个 (m)，非常不自然，应该是别有用心，所以可以猜测这个式子其实是有其他含义的。
发现式子可以改写成
[sum_{i=1}^m sum_{j=i+1}^m (a_{b_i}+a_{b_j}-2 f(min (b_i,b_j),max (b_i,b_j)))
]
这个权值长得很像树上两点的距离，而发现笛卡尔树恰好满足这个性质。所以建出笛卡尔树然后 (dp) 即可。
#include<stdio.h>
#include<algorithm>
using namespace std;
inline int read(){
int x=0,flag=1; char c=getchar();
while(c<'0'||c>'9'){if(c=='-')flag=0;c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-48;c=getchar();}
return flag? x:-x;
}
typedef long long ll;
const int N=4e3+7;
struct Node{
int ls,rs;
}t[N];
ll dp[N][N];
int a[N],top=0,st[N],sz[N],n,m;
void dfs(int u){
sz[u]=1;
if(t[u].ls){
dfs(t[u].ls);
const int v=t[u].ls;
for(int i=sz[u];~i;i--)
for(int j=0,rg=min(sz[v],m-i);j<=rg;j++)
dp[u][i+j]=max(dp[u][i+j],dp[u][i]+dp[v][j]+1ll*j*(m-j)*(a[v]-a[u]));
sz[u]+=sz[v];
}
if(t[u].rs){
dfs(t[u].rs);
const int v=t[u].rs;
for(int i=sz[u];~i;i--)
for(int j=0,rg=min(sz[v],m-i);j<=rg;j++)
dp[u][i+j]=max(dp[u][i+j],dp[u][i]+dp[v][j]+1ll*j*(m-j)*(a[v]-a[u]));
sz[u]+=sz[v];
}
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read(); int ret=0;
while(top&&a[st[top]]>=a[i])
ret=st[top--];
if(ret) t[i].ls=ret;
if(top) t[st[top]].rs=i;
st[++top]=i;
}
dfs(st[1]); printf("%lld",dp[st[1]][m]);
}