在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
4 4 5 9 4
43 54
区间dp，不过是圆形的，把他们分成一个n*2的区间就好，然后进行区间dp ，对dp1不能全设成最大值，不然没法取min。
最后要在所有区间长度为n的区间中取出最大值与最小值。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 const int MAXN = 210; 6 int dp1[MAXN][MAXN],dp2[MAXN][MAXN],a[MAXN],sum[MAXN]; 7 int n,ans1 = 2147483647,ans2 = 0; 8 9 int main() 10 { 11 scanf("%d",&n); 12 for (int i=1; i<=n*2; ++i) 13 for (int j=i+1; j<=n*2; ++j) 14 dp1[i][j] = 1e8; //最小值 15 memset(dp2,0,sizeof(dp2)); //最大值 16 for (int i=1; i<=n; ++i) 17 { 18 scanf("%d",&a[i]); 19 a[i+n] = a[i]; 20 } 21 for (int i=1; i<=n*2; ++i) 22 sum[i] = sum[i-1]+a[i]; 23 for (int i=2*n-1; i>=1; --i)//从倒数第二个开始枚举左端点 24 for (int j=i+1; j<=2*n; ++j)//枚举右端点 25 for (int k=i; k<=j-1; ++k)//枚举中间点 26 dp1[i][j] = min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]), 27 dp2[i][j] = max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]); 28 for (int i=1; i<=n; ++i) 29 { 30 ans1 = min(ans1,dp1[i][i+n-1]); 31 ans2 = max(ans2,dp2[i][i+n-1]); 32 } 33 printf("%d\n%d",ans1,ans2); 34 return 0; 35 }
原文：http://www.cnblogs.com/mjtcn/p/7197526.html