在一个圆形操场的四周摆放N堆石子(N≤100)，现要将石子有次序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。编一程序，读入堆数N及每堆石子数(≤100)选择一种合并石子的方案，分别得到合并这N堆石子为一堆，可以得到的最大得分和最小得分。用c++编程

以下是用C++编写的解决方案：

#include <iostream>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
int n;
int w[105], s[105];
int dp_max[105][105], dp_min[105][105];

int main() {
    cin >> n;
    memset(dp_max, -INF, sizeof(dp_max));
    memset(dp_min, INF, sizeof(dp_min));
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        s[i] = s[i - 1] + w[i];
        dp_max[i][i] = dp_min[i][i] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                dp_max[i][j] = max(dp_max[i][j], dp_max[i][k] + dp_max[k + 1][j] + s[j] - s[i - 1]);
                dp_min[i][j] = min(dp_min[i][j], dp_min[i][k] + dp_min[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    cout << dp_max[1][n] << endl << dp_min[1][n] << endl;
    return 0;
}

这个问题可以用动态规划来解决。状态转移方程如下：

$$dp_{max}(i,j)=\max_{i\leq k<j}\{dp_{max}(i,k)+dp_{max}(k+1,j)+\sum_{t=i}^jw_t\}$$

$$dp_{min}(i,j)=\min_{i\leq k<j}\{dp_{min}(i,k)+dp_{min}(k+1,j)+\sum_{t=i}^jw_t\}$$

其中$dp_{max}(i,j)$表示将第$i$堆到第$j$堆合并为一堆所能得到的最大得分，$dp_{min}(i,j)$表示将第$i$堆到第$j$堆合并为一堆所能得到的最小得分。$w_t$表示第$t$堆的石子数。

在代码中，我们用$s_i$表示前$i$堆的石子数之和，以便在计算得分时方便计算。同时，我们用$dp_{max}$和$dp_{min}$数组分别记录最大得分和最小得分。在初始化时，$dp_{max}(i,i)=dp_{min}(i,i)=0$，即一堆石子合并为一堆不需要得分。最后，$dp_{max}(1,n)$即为最大得分，$dp_{min}(1,n)$即为最小得分。

时间复杂度为$O(n^3)$，可以通过本题。