这竟然是一道区间dp……一开始我按照普通dp做的……于是咳咳……
我一开始枚举左端点 i ，右端点 j ，在枚举中间的任意一个 k ，一直取最大值，但是 “ 显然不对 ” 。
那为什么呢？
就是因为：
在处理 i 到 j 的时候，我们并不知道 k 到 j 的最优解，所以这次我们就没用到本应该用到的值来更新现有解，自然不对。
这就需要区间dp了，先枚举长度，这样所有小的长度都会被提前修改，这样就保证了以后用到的都是最优解。
再用前缀和优化一下，每一次 i 到 j 都要加上 i 到 j 的果子总数，因为相当于进行了一次合并，而里面现在具体进行的合并，就是那个 f [ x ] [ y ] ，在我们枚举小长度的时候，就已经加过一遍二者果子数之和了，现在可以直接用。（不太好解释，感性理解一下）
下面附上代码：
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define maxn 2000 int n,val[maxn],pl[maxn],num[maxn]; int fax[maxn][maxn],fin[maxn][maxn]; int find(int a,int b) { return pl[b]-pl[a-1]; } int main() { int ans=0,ANS=9999999999; scanf("%d",&n); for(int i=1; i<=n; i++) { scanf("%d",&num[i]); pl[i]=pl[i-1]+num[i]; num[i+n]=num[i]; } for(int i=n+1; i<=n*2; i++) pl[i]=pl[i-1]+num[i]; for(int p=1; p<n; p++) for(int i=1,j=p+i; i<2*n&&j<=2*n; i++,j=p+i) { fin[i][j]=999999999; for(int k=i; k<j; k++) { fax[i][j]=max(fax[i][j],fax[i][k]+fax[k+1][j]+find(i,j)); fin[i][j]=min(fin[i][j],fin[i][k]+fin[k+1][j]+find(i,j)); } } for(int i=1; i<=n+1; i++) { ans=max(ans,fax[i][i+n-1]); ANS=min(ANS,fin[i][i+n-1]); } printf("%d\n%d",ANS,ans); return 0; }
原文：https://www.cnblogs.com/popo-black-cat/p/10331620.html