Description
在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分和最大得分。对于给定n堆石子,计算合并成一堆的最小得分和最大得分。
Input
输入数据的第1行是正整数n,1≤n≤100,表示有n堆石子。第二行有n个数,分别表示每堆石子的个数。Output
输出数据有两行,第1行中的数是最小得分,第2行中的数是最大得分。Sample
Input
4 4 4 5 9
Output
43 54
1 #include <stdio.h> 2 #include <iostream> 3 #include <memory> 4 #include <algorithm> 5 #include <string.h> 6 7 #define inf 0x3f3f3f3f 8 9 using namespace std; 10 11 int main() 12 { 13 int n, i, j, k, maxx, minn; 14 int a[205], dp1[205][205], dp2[205][205], sum[205]; 15 cin >> n; 16 for(i=1; i<=n; i++) 17 { 18 cin >> a[i]; 19 a[i+n] = a[i]; 20 } 21 sum[0] = 0; 22 for(i=1; i<=2*n; i++) 23 { 24 sum[i] = sum[i-1] + a[i]; 25 } 26 memset(dp1, 0, sizeof(dp1)); 27 memset(dp2, 0, sizeof(dp2)); 28 for(i=2*n; i>=1; i--) 29 { 30 for(j=i+1;j<=2*n&&j<i+n; j++) 31 { 32 dp2[i][j] = inf; 33 for(k=i;k+1<=j;k++) 34 { 35 dp1[i][j] = max(dp1[i][j], dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]); 36 dp2[i][j] = min(dp2[i][j], dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]); 37 } 38 } 39 } 40 minn = inf; 41 maxx = 0; 42 for(i=1;i<n;i++) 43 { 44 maxx = max(maxx, dp1[i][i+n-1]); 45 minn = min(minn, dp2[i][i+n-1]); 46 } 47 cout << minn << endl << maxx << endl; 48 return 0; 49 }