题目分析
将石子堆排成一圈后，每次合并相邻的两堆石子，记得分为一次合并堆的石子，求最大得分和最小的分
由于圆形排列的石子堆可以视为首尾元素可合并的直线排列，所以直接分析直线石子堆
解题方法
石子堆合并的最后一次记分为：数组仅剩两个元素，最后一次记分为0号与1号元素相加
石子堆合并的过程中，要想保证最后的得分最小，则需要保证每次合并的两堆石子之和是最小的。 因此：
设置当前数组为stone
两两相邻的合并结果为nstone
找到最小的合并结果后，将其他元素替换为剩余的元素，将数组大小-1
全局变量的值加上每次合并后被保留的结果
Stone：
|
4 |
4 |
5 |
9 |
Nstone:
|
8 |
9 |
14 |
13 |
|
8 |
5 |
9 |
完成递归后，可得到最小记分，最大记分同理
运行结果
代码
#include <iostream> #include <cmath> #include <algorithm> #include <cstdlib> using namespace std; int n; int r = 0; void minsum(int *stone, int size) { if (size == 2) { r+=(stone[0] + stone[1]); } else { int nstone[100]; int min = 0, mi = 0; for (int i = 0; i < size - 1; i++) { nstone[i] = stone[i] + stone[i + 1]; if (nstone[i] <= min) { min = nstone[i]; mi = i; } } for (int i = 0, j = 0; i < size-1; i++,j++) { if (i > mi) { nstone[i] = stone[i + 1]; } else if (i < mi) { nstone[i] = stone[i]; } else { r += nstone[i]; } } minsum(nstone, size - 1); } } void maxsum(int *stone, int size) { if (size == 2) { r += (stone[0] + stone[1]); } else { int nstone[100]; int max = 0, mi = 0; for (int i = 0; i < size - 1; i++) { nstone[i] = stone[i] + stone[i + 1]; if (nstone[i] > max) { max = nstone[i]; mi = i; } } for (int i = 0, j = 0; i < size - 1; i++, j++) { if (i > mi) { nstone[i] = stone[i + 1]; } else if (i < mi) { nstone[i] = stone[i]; } else { r += nstone[i]; } } maxsum(nstone, size - 1); } } int main() { cin >> n; int stone[100]; for (int i = 0; i < n; i++) { cin >> stone[i]; } r = 0; minsum(stone, n); cout << r << endl; r = 0; maxsum(stone, n); cout << r << endl; getchar(); }