题目描述 Description
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入描述 Input Description
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出描述 Output Description
输出共2行,第1行为最小得分,第2行为最大得分.
样例输入 Sample Input
4
4 4 5 9
样例输出 Sample Output
43
54
数据范围及提示 Data Size & Hint
经典的区间动态规划。
1 #include <algorithm> 2 #include <cstdio> 3 #define N 1015 4 5 using namespace std; 6 7 bool if_; 8 char ch; 9 int n,num[N]; 10 int maxn,minn=1e7; 11 int f_max[N][N],f_min[N][N]; 12 13 void read(int &x) 14 { 15 if_=0;x=0; 16 ch=getchar(); 17 while(ch<'0'||ch>'9') 18 { 19 if(ch=='-') if_=1; 20 ch=getchar(); 21 } 22 while(ch>='0'&&ch<='9') 23 { 24 x=x*10+ch-'0'; 25 ch=getchar(); 26 } 27 if(if_) x=(~x)+1; 28 } 29 30 int main() 31 { 32 read(n); 33 for(int i=1;i<=n;i++) 34 read(num[i]),num[i+n]=num[i],num[i]+=num[i-1]; 35 for(int i=n+1;i<=n*2;i++) num[i]+=num[i-1]; 36 for(int i=1;i<=n;i++) 37 f_min[i][i]=f_max[i][i]=0; 38 for(int len=2;len<=n;len++) 39 for(int i=2*n-len;i>=1;i--) 40 { 41 int j=len+i-1; 42 f_min[i][j]=1e7; 43 f_max[i][j]=0; 44 for(int k=i;k<j;k++) 45 { 46 f_min[i][j]=min(f_min[i][j],f_min[i][k]+f_min[k+1][j]+num[j]-num[i-1]); 47 f_max[i][j]=max(f_max[i][j],f_max[i][k]+f_max[k+1][j]+num[j]-num[i-1]); 48 } 49 } 50 for(int i=1;i<=n;i++) 51 { 52 if(f_min[i][i+n-1]<minn) minn=f_min[i][i+n-1]; 53 if(f_max[i][i+n-1]>maxn) maxn=f_max[i][i+n-1]; 54 } 55 printf("%d %d",minn,maxn); 56 return 0; 57 }