题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：输出共2行,第1行为最小得分,第2行为最大得分.
输入输出样例
输入样例：
1 42 4 5 9 4
输出样例：
1 432 54
这道题的动态规划还是很好想的~，这道题就是普通的区间dp。
用point[i][j]来表示（i，j）区间内得分得最大值或最小值，然后用k将（i，j）区间分开，这个（i，j）区间得分的最大值（最小值）就是，对于k取（i，j）区间中的任意一个值时（i，k）区间和（k+1，j）区间相加的最大值（最小值）。如果（i，j）区间内只有两个值，则得分就是这两堆石头之和。
dp方程：point[ i ][ j ] = max(min)(point[ i ][ j ] , point[ i ][ k ] + point[ k + 1 ][ j ]);
这样就完事啦，但是要注意！！！这道题的石堆围成了个圈！！！（导致我第一次没过QAQ）
最后贴上自己的代码
1 #include2 #include 3 using namespace std; 4 int N; 5 int stone[101]; 6 int point[101][101]; 7 int stoneSum[101][101]{ 0 }; 8 9 int max(int a, int b) { return a > b ? a : b; } 10 int min(int a, int b) { return a > b ? b : a; } 11 int partStoneMax(int front, int rear);//一个环切成两段 12 int partstonemax(int front, int rear); 13 int partStoneMin(int front, int rear);//同上 14 int partstonemin(int front, int rear); 15 16 int main() { 17 int sum; 18 cin >> N; 19 for (int i = 1; i <= N; i++) 20 cin >> stone[i]; 21 for (int i = 1; i <= N; i++) 22 for (int j = 1; j <= N; j++) 23 point[i][j] = -1; 24 for (int i = 1; i <= N; i++) 25 for (int j = 1; j <= N; j++) { 26 sum = 0; 27 int k = i; 28 while (1) { 29 sum += stone[k]; 30 if (k == j) break; 31 if (k == N) k = 0; 32 k++; 33 } 34 stoneSum[i][j] = sum; 35 } 36 cout << partStoneMin(1, N) << endl; 37 for (int i = 1; i <= N; i++) 38 for (int j = 1; j <= N; j++) 39 point[i][j] = -1; 40 cout << partStoneMax(1, N) << endl; 41 system("PAUSE"); 42 return 0; 43 } 44 45 int partStoneMax(int front, int rear) { 46 int p = 0, temp = 0; 47 for (int i = 1; i < N; i++) 48 for (int j = i; j < N; j++) { 49 temp = partstonemax(i, j) + partstonemax(j + 1, i - 1); 50 p = max(p, temp); 51 } 52 point[front][rear] = p + stoneSum[front][rear]; 53 return point[front][rear]; 54 } 55 56 int partstonemax(int front, int rear) { 57 if (front > N)front = 1; 58 if (rear < 1)rear = N; 59 int p = 0, k = front, temp; 60 if (point[front][rear] >= 0) 61 return point[front][rear]; 62 if (front == rear) { 63 point[front][rear] = 0; 64 return 0; 65 } 66 while (1) { 67 if (k == rear) break; 68 temp = partstonemax(front, k) + partstonemax(k + 1, rear); 69 p = max(p, temp); 70 if (k == N) k = 0; 71 k++; 72 } 73 p += stoneSum[front][rear]; 74 point[front][rear] = p; 75 return p; 76 } 77 78 int partStoneMin(int front, int rear) { 79 int p = 99999999, temp = 0; 80 for (int i = 1; i < N; i++) 81 for (int j = i; j < N; j++) { 82 temp = partstonemin(i, j) + partstonemin(j + 1, i - 1); 83 p = min(p, temp); 84 } 85 point[front][rear] = p + stoneSum[front][rear]; 86 return point[front][rear]; 87 } 88 89 int partstonemin(int front, int rear) { 90 if (front > N)front = 1; 91 if (rear < 1)rear = N; 92 int p = 99999999, k = front, temp; 93 if (point[front][rear] >= 0) 94 return point[front][rear]; 95 if (front == rear) { 96 point[front][rear] = 0; 97 return 0; 98 } 99 while (1) {100 if (k == rear) break;101 temp = partstonemin(front, k) + partstonemin(k + 1, rear);102 p = min(p, temp);103 if (k == N) k = 0;104 k++;105 }106 p += stoneSum[front][rear];107 point[front][rear] = p;108 return p;109 }
只能想出ms的laji的我。。。
我是萌新，我是萌新，不要说（我）代码了QAQ