<—点个赞吧QwQ

宣传一下算法提高课整理{:target=”_blank”}

将 $n$ 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

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

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

输入格式

第一行包含整数 $n$，表示共有 $n$ 堆石子。

第二行包含 $n$ 个整数，分别表示每堆石子的数量。

输出格式

输出共两行：

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

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

数据范围

$1 \\le n \\le 200$

输入样例：

4
4 5 9 4

输出样例：

43
54

思路

这一题其实跟石子合并是一样的，关键就在如何拆环。
我们可以复制一个数组在$a$数组后面，然后答案就是$\underset{1\le i \le n + 1}\min\lbrace f_{i,i + n - 1}\rbrace$和$\underset{1\le i \le n + 1}\max\lbrace f_{i,i + n - 1}\rbrace$。

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 410;
int n;
int a[N];
int s[N];
int f[N][N],g[N][N];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    memset (g,0x3f,sizeof (g));
    for (int i = 1;i <= 2 * n;i++) {
        s[i] = s[i - 1] + a[i];
        f[i][i] = g[i][i] = 0;
    }
    for (int len = 2;len <= n;len++) {  //枚举到n就可以了
        for (int i = 1;i + len - 1 <= 2 * n;i++) {
            int j = i + len - 1;
            for (int k = i;k <= j - 1;k++) {
                f[i][j] = max (f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                g[i][j] = min (g[i][j],g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    int ans1 = 0,ans2 = 2e9;
    for (int i = 1;i <= n + 1;i++) {
        ans1 = max (ans1,f[i][i + n - 1]);
        ans2 = min (ans2,g[i][i + n - 1]);
    }
    cout << ans2 << endl << ans1 << endl;
    return 0;
}