python/TangDou/AcWing/Section/1068.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 410; // 准备两倍的空间
const int INF = 0x3f3f3f3f;
int n;       // n个节点
int s[N];    // 前缀和
int a[N];    // 记录每个节点的石子数量
int f[N][N]; // 区间DP的数组(最大值)
int g[N][N]; // 区间DP的数组(最小值)

// 环形DP：通用办法
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i + n] = a[i]; // 复制后半段的数组,构建一个长度为2*n的数组，环形DP问题的处理技巧
    // 预处理前缀和
    for (int i = 1; i <= n * 2; i++) s[i] = s[i - 1] + a[i];

    // 预求最小，先放最大
    memset(f, 0x3f, sizeof f);

    // 预求最大，先放最小
    memset(g, -0x3f, sizeof g);

    // len=1时，代价0
    for (int i = 1; i <= 2 * n; i++) f[i][i] = g[i][i] = 0;

    // 区间DP的迭代式经典写法
    for (int len = 2; len <= n; len++)               // 枚举区间长度
        for (int l = 1; l + len - 1 <= n * 2; l++) { // 枚举左端点
            // 计算出右端点
            int r = l + len - 1;
            // 枚举分界点k
            for (int k = l; k < r; k++) {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    // 因为从哪个位置断开环都是可行的，所以，我们依次检查一下
    int Min = INF, Max = -INF;
    for (int i = 1; i <= n; i++) {
        Min = min(Min, f[i][i + n - 1]);
        Max = max(Max, g[i][i + n - 1]);
    }
    // 输出
    printf("%d\n%d\n", Min, Max);
    return 0;
}