D - Subsequence
发现\(f(i,j)\)不好处理，考虑将其转换成另一个函数
考虑笛卡尔树，\(\min(a_i,a_{i+1},...,a_j)\)就是在笛卡尔树上，\(i\)和\(j\)的\(lca\)
那么就可以将问题转移到笛卡尔树上，设\(dp[x][c]\)表示以\(x\)所处的子树中，选了\(c\)个的最大价值
那么显然有：
\[dp[x][i+j]=\max(dp[x][i+j],dp[ls[x]][i]+dp[rs[x]][j]-
2\times i\times j\times a[x])\\
dp[x][i+j+1]=\max(dp[x][i+j+1],dp[ls[x]][i]+
dp[rs[x]][j]+1\times m\times a[x]-(2\times i\times j+(i+j)\times 2+1)\times a[x]);
\]
复杂度：看似\(O(NM^2)\)实则\(O(NM)\)
树卷积相关理论可证
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e3+5;
const ll INF=1e18;
int n,m,a[N];
int ls[N],rs[N],stk[N],top,sz[N];
ll dp[N][N];
void dfs(int x){
sz[x]=1;
if(ls[x]) dfs(ls[x]),sz[x]+=sz[ls[x]];
if(rs[x]) dfs(rs[x]),sz[x]+=sz[rs[x]];
for(int i=0;i<=min(m,sz[x]);++i) dp[x][i]=-INF;
for(int i=0;i<=min(m,sz[ls[x]]);++i)
for(int j=0;j<=sz[rs[x]]&&i+j<=m;++j){
dp[x][i+j]=max(dp[x][i+j],dp[ls[x]][i]+dp[rs[x]][j]-2ll*i*j*a[x]);
if(i+j+1<=m) dp[x][i+j+1]=max(dp[x][i+j+1],dp[ls[x]][i]+dp[rs[x]][j]+1ll*m*a[x]-(2ll*i*j+(i+j)*2ll+1ll)*a[x]);
}
}
int main(){//
scanf("%d%d",&n,&m);
for(int i=1,k;i<=n;++i){
scanf("%d",&a[i]),k=top;
while(k&&a[stk[k]]>a[i]) --k;
if(k) rs[stk[k]]=i;
if(k<top) ls[i]=stk[k+1];
stk[++k]=i,top=k;
}
dfs(stk[1]);
printf("%lld",dp[stk[1]][m]);
return 0;
}