问题描述：在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆，规定每次只能选相邻的2堆石子合并成一堆，并将新的堆石子数记为该次合并的得分。试设计一个算法，计算出将n堆石子合并成一堆的最小得分和最大得分。

算法设计：对于给定n堆石子，计算合并成一堆的最小得分和最大得分。

数据输入：由文件 input.txt 提供输入数据。文件的第1行是正整数$n(1\leq n \leq 100)$，表示有n堆石子。第2行有n个数，分别表示每堆石子的个数。

结果输出：将计算结果输出到文件 output.txt。文件第1行的数是最小得分，第1行中的数是最大得分。
&nbsp

#include<iostream>
#include<vector>
using namespace std;
#define MAXN 100010
/*
联系例题--矩阵链乘，一毛一样
4
4 4 5 9
圆形操场，代表第一堆石子与最后一堆石子相邻。直接将数组定义为[4,4,5,9,4,4,5,9],就可以用[...9，4...]代表头尾相连；因此可以设数组长度为2n,数组下标为0~2n-1，但遍历数组时，宽度最大还是n
设dp[i][j]表示第i个石堆到第j个石堆合并的最小分;weight[i]表示前i个石堆的重量,weight[0]=0;
假设dp[i][j]是由i~k和k+1~j合并得到的，则有dp[i][j]=min(dp[i][k]+dp[k+1][j]+(weight[j]-weight[i-1]));
*/

int n;//石堆数
int weight[MAXN];//前i个石堆累积重量
vector<vector<int>> dp;
void init() {
    cin >> n;
    weight[0] = 0;
    for (int i = 1; i <= n; i++) { cin >> weight[i];
    }
    for (int i = n + 1; i <= 2 * n; i++) {
        weight[i] = weight[i - n];
    }
    for (int i = 1; i <= 2*n; i++) {
        weight[i] += weight[i - 1];//0,4,8,13,22.26,30,35,44
    }
    int m = 2 * n;
    dp.resize(m, vector(m, 1e9));
    for (int i = 0; i < m; i++) {
        dp[i][i] = 0;//只有一堆合并不了，得分为0
    }
}
void solve_min_score() {
    //填数组
    //因为计算dp[i][j]要先计算dp[i][k]和dp[k+1][j]。计算大区间要先计算小区间，因此最外层循环枚举len长度，确保在后面计算大区间时已经有了小区间的dp值。
    for (int len = 2; len <= 2 * n; len++) {//枚举区间长度，长度为1表示一堆石堆，因此不用考虑
        for (int i = 0; i <= 2 * n - len; i++) {//枚举左端点
            int j = i + len - 1;//右端点
            for (int k = i; k < j; k++) {//枚举分割点
                dp[i][j] = min(dp[i][j] ,dp[i][k] + dp[k + 1][j] + weight[j+1] - weight[i]);
            }
        }
    }
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++) {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
     }
    // 计算最小得分

    int min_score = 1e9;
    for (int i = 0; i < n; i++) { // 枚举所有长度为 n 的环形区间
        min_score = min(min_score, dp[i][i + n - 1]);
    }
    cout << min_score << endl;
}

int main() {
    init();
    solve_min_score();
    return 0;
}