石子合并

题目描述

将 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 $N$ 及每堆的石子数，并进行如下计算：

1. 选择一种合并石子的方案，使得做 $N - 1$ 次合并得分总和最大。
2. 选择一种合并石子的方案，使得做 $N - 1$ 次合并得分总和最小。

输入描述

输入第一行一个整数 $N$ $(1≤N≤100)$，表示有 $N$ 堆石子。

第二行 $N$ 个整数，表示每堆石子的数量。

输出描述

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

测试用例

输入

4
4 5 9 4

输出

43
54

#include <bits/stdc++.h>
using namespace std;
#define MAXN 210
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
ll a[MAXN],sum[MAXN],dpmax[MAXN][MAXN], dpmin[MAXN][MAXN];
ll ansmax = 0, ansmin = INF,n;
int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    for (ll i = n + 1; i <= 2 * n; i++) {
        a[i] = a[i - n];
        sum[i] = sum[i - 1] + a[i];
    }
    for (ll k = 2; k <= n; k++) {
        for (ll i = 1; i <= 2 * n - k + 1; i++) {
            ll l = i, r = i + k - 1;
            dpmin[l][r] = INF;
            for (ll j = 1; j < k; j++) {
                ll mid = i + j - 1;
                dpmax[l][r] = max(dpmax[l][r], dpmax[l][mid] + dpmax[mid + 1][r] + sum[r] - sum[l - 1]);
                dpmin[l][r] = min(dpmin[l][r], dpmin[l][mid] + dpmin[mid + 1][r] + sum[r] - sum[l - 1]);
            }
            if (k == n) {  //取出区间长度为n的最小值和最大值
                ansmax = max(ansmax, dpmax[l][r]);
                ansmin = min(ansmin, dpmin[l][r]);
            }
        }
    }
    cout << ansmin << "\n";  //最小
    cout << ansmax;  //最大
    return 0;
}