题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输出样例#1：
43
54
解题思路:
一道环形DP,f[i][j]表示i到j这一段合并成一堆的最大值，f[i][j] = max(f[i][j], f[i][k] + f[k+1][j] + sum[i+1][j]) i<=k<j,对于环形的处理是把这个环复制,接到末尾,其中sum[i+1][j]表示a[i] + a[i+1] + .. + a[j].
AC代码:
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 using namespace std; 5 int n,f1[210][210],f2[210][210],num[210],maxans,minans = 9999999,he[105];//f1为最大值,f2为最小值 6 int max(int a,int b) { 7 if(a >= b) return a; 8 else return b; 9 } 10 int min(int a,int b) { 11 if(a <= b) return a; 12 else return b; 13 } 14 int main() 15 { 16 cin >> n; 17 memset(f2,0x7f7f7f,sizeof(f2));//将最小值初始位足够大 18 for(int i = 1; i <= n; i++) {//读入 19 scanf("%d",&num[i]); 20 he[i] = he[i-1] + num[i]; 21 f2[i][i] = 0; 22 } 23 for(int i = n+1; i <= n+n; i++) {//将这个环复制一遍接到末尾 24 num[i] = num[i-n]; 25 he[i] = he[i-1] + num[i]; 26 f2[i][i] = 0; 27 } 28 for(int p = 1; p < n; p++)//枚举区间长度 29 for(int i = 1, j = i + p; i < n + n && j < n + n; i++, j = i + p)//枚举起点和终点 30 for(int k = i; k < j; k++){//设置断点 31 f1[i][j] = max(f1[i][j], f1[i][k] + f1[k+1][j] + he[j] - he[i-1]);//状态转移 32 f2[i][j] = min(f2[i][j], f2[i][k] + f2[k+1][j] + he[j] - he[i-1]);//状态转移 33 } 34 35 for(int i = 1; i <= n; i++) {//找最大值和最小值 36 maxans = max(maxans,f1[i][i+n-1]); 37 minans = min(minans,f2[i][i+n-1]); 38 } 39 printf("%d %d",minans,maxans); 40 41 42 return 0; 43 }