题目传送门
考虑朴素的 dp 方程 \(f[i][j]=\min f[i][k]+f[k+1][j]+sum[j]-sum[i-1]\)。先证明四边形不等式，证明决策单调性的范围 \(p[i][j-1]\le p[i][j]\le p[i+1][j]\)。复杂度是因为中间都消掉了，所以就是状态数 \(O(n^2)\)。
#include<bits/stdc++.h>
using namespace std;
#define L(i,l,r) for(int i=l;i<=r;++i)
#define R(i,l,r) for(int i=r;i>=l;--i)
const int N=5010;
int n,f[N][N],s[N],p[N][N];
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
// cout.tie(0);
scanf("%d",&n);
L(i, 1, n){
scanf("%d",s+i);
s[i]+=s[i-1];
}
L(i, 1, n)p[i][i]=i;
L(len, 2, n)
L(i, 1, n-len+1){
int j=i+len-1;
f[i][j]=1e9;
L(k, p[i][j-1], p[i+1][j]){
int tmp=f[i][k]+f[k+1][j]+s[j]-s[i-1];
if(tmp<f[i][j]){
f[i][j]=tmp;
p[i][j]=k;
}
}
}
printf("%d",f[1][n]);
return 0;
}