P1880 [NOI1995]石子合并

Link

Solution

区间dp

Code

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

int dpmax[210][210], dpmin[210][210], a[210], ps[210];

int main() {
    int n;
    cin >> n;
    memset(dpmin, 0x3f3f3f3f, sizeof(dpmin));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i + n] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++) dpmin[i][i] = 0, ps[i] = ps[i - 1] + a[i];
    for (int len = 1; len <= n; len++) {
        for (int i = 1; len + i - 1 <= 2 * n; i++) {
            int j = len + i - 1;
            for (int k = i; k < j && k <= 2 * n; k++)
                dpmax[i][j] = max(dpmax[i][j], dpmax[i][k] + dpmax[k + 1][j] + ps[j] - ps[i - 1]),
                dpmin[i][j] = min(dpmin[i][j], dpmin[i][k] + dpmin[k + 1][j] + ps[j] - ps[i - 1]);
        }
    }
    int minv = 0x3f3f3f3f, maxv = 0;
    for (int i = 1; i <= n; i++)
        maxv = max(maxv, dpmax[i][i + n - 1]), minv = min(minv, dpmin[i][i + n - 1]);
    cout << minv << '\n' << maxv << endl;
    return 0;
}