在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
4 4 5 9 4
43 54
区间动态规划
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; inline int min(int x,int y) { if(x<y)return x;return y; } inline int max(int x,int y) { if(y>x)return y;return x; } int a[203]; int dp_max[203][203]; int dp_min[203][203]; int main() { int n; scanf("%d",&n); memset(dp_max,0,sizeof(dp_max)); for(int i=1;i<=2*n;i++) for(int j=i+1;j<=2*n;j++) dp_min[i][j]=0x7fffffff; for(int i=1;i<=n;i++)scanf("%d",a+i),a[i+n]=a[i]; for(int i=2;i<=n*2;i++)a[i]+=a[i-1]; for(int i=n*2-1;i>=1;i--) { for(int j=i+1;j<=n*2;j++) { for(int k=i;k<j;k++) { dp_min[i][j]=min(dp_min[i][j],dp_min[i][k]+dp_min[k+1][j]+a[j]-a[i-1]); dp_max[i][j]=max(dp_max[i][j],dp_max[i][k]+dp_max[k+1][j]+a[j]-a[i-1]); } } } int minn=0x7fffffff; int maxx=-1; for(int i=1;i<=n;++i) { minn=min(dp_min[i][i+n-1],minn); maxx=max(dp_max[i][i+n-1],maxx); } printf("%d\n%d",minn,maxx); return 0; }
原文：http://www.cnblogs.com/sssy/p/7197547.html