题意：给n堆石子，每次合并相邻两堆，花费是这两堆的石子个数之和（1和n相邻），求全部合并，最小总花费
若不要求相邻，可以贪心地合并最小的两堆。然而要求相邻就有反例
为了方便，我们可以把n个数再复制一遍，放到第n个数后，就不用考虑环的问题了
我们设f[i][j]为合并区间[i,j]所需要的最小花费，然后就可以得到
f[i][j]=min{f[i][k]+f[k+1][j]+sum[i,j]} ,i<=k<=j,i<j;
f[i][i]=0
然后就可以用$O(n^3)$的复杂度递推啦。此题结束。
然而n<=1000...
四边形不等式：
若f[i][j]=min{f[i][k]+f[k+1][j]+w[i][j]} ,i<=k<=j；
s[i][j]为使f[i][j]取到最小值的k ，其中有(a<=b<=c<=d)
1.w[b][c]<=w[a][d] （w满足区间包含单调性）
2.w[a][c]+w[b][d]<=w[b][c]+w[a][d] （w满足四边形不等式）
则f也满足四边形不等式（*）
所以s[i][j-1]<=s[i][j]<=s[i+1][j] （**）
*、**:太麻烦了不证了！
于是就可以优化刚才的dp（sum显然满足以上两点），每次的k不是从i枚举到j，而是从s[i][j-1]枚举到s[i+1][j]，这样，平摊下来，就可以在O(1)复杂度完成f[i][j]的计算
然而我很沙雕的设f[i][j]表示长度为i，从j开始的区间了..虽然影响不大但是感觉写起来变得有点迷
然后按照我的写法，n=1的时候是要特判的...
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 #include<queue> 6 #include<cmath> 7 #define LL long long int 8 #define inf 0x3f3f3f3f 9 using namespace std; 10 const int maxn=2010; 11 12 LL rd(){ 13 LL x=0;char c=getchar();int neg=1; 14 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();} 15 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 16 return x*neg; 17 } 18 19 int N,num[maxn]; 20 int f[maxn][maxn][2],sum[maxn]; 21 22 int main(){ 23 int i,j,k; 24 while(~scanf("%d",&N)){ 25 int ans=inf; 26 for(i=1;i<=N;i++) num[i+N]=num[i]=rd(); 27 if(N==1){printf("0 ");continue;} 28 for(i=1;i<=2*N;i++) sum[i]=sum[i-1]+num[i],f[1][i][1]=i; 29 for(i=2;i<=N;i++){ 30 for(j=1;j<2*N-i+1;j++){ 31 f[i][j][0]=inf; 32 for(k=f[i-1][j][1];k<=f[i-1][j+1][1];k++){ 33 int a=f[k-j+1][j][0]+f[i-k+j-1][k+1][0]; 34 if(a<f[i][j][0]) f[i][j][0]=a,f[i][j][1]=k; 35 }f[i][j][0]+=sum[i+j-1]-sum[j-1]; 36 if(i==N) ans=min(ans,f[i][j][0]); 37 } 38 }printf("%d ",ans); 39 } 40 41 return 0; 42 }