本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1880
本来以为是一道简单的区间DP问题，草草地写了个程序结果样例都没过，仔细一看，原来n堆石子摆成了环。区间DP是线性DP的一种，写法比较固定，一般是先枚举区间长度，再枚举区间左端点，推出区间右端点，状态转移通常是枚举中间点。这道题虽然成了环，但本质是不变的，还是从2到n枚举区间长度，只不过区间左端点可以是1到n，区间右端点可以在左端点左侧。为了方便起见，我们可以直接把环变为链跑区间DP，仔细想想，可以把长度为n的环用长度为2*n-1的链来代替。只不过这样，就不能方便的把dp[1][n]作为答案了，而是当区间长度枚举到n时，用每次求出dp值更新答案。详见代码。
1 #include<cstdio> 2 const int maxn=105; 3 int n,num[2*maxn],sum[2*maxn],dp1[2*maxn][2*maxn],dp2[2*maxn][2*maxn],ans1=0x3f3f3f3f,ans2; 4 inline int min(int a,int b) {return a<b?a:b;} 5 inline int max(int a,int b) {return a>b?a:b;} 6 int main() { 7 scanf("%d",&n); 8 for(int i=1;i<=n;++i) {scanf("%d",&num[i]);num[n+i]=num[i];} 9 for(int i=1;i<=2*n;++i) sum[i]=sum[i-1]+num[i]; 10 for(int l=2;l<=n;++l) 11 for(int i=1;i<=2*n-l;++i) { 12 int j=i+l-1; 13 dp1[i][j]=0x3f3f3f3f; 14 for(int k=i;k<j;++k) { 15 dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]); 16 dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]); 17 } 18 dp1[i][j]+=sum[j]-sum[i-1];dp2[i][j]+=sum[j]-sum[i-1]; 19 if(l==n) {ans1=min(ans1,dp1[i][j]);ans2=max(ans2,dp2[i][j]);} 20 } 21 printf("%d\n%d",ans1,ans2); 22 return 0; 23 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9602427.html
