题目分析

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 410;
int w[N] , sum[N];
int f[N][N] , g[N][N];
int n;
int main() {

    cin >> n;
    memset(f,0x3f,sizeof f);
    memset(g,-0x3f,sizeof g);
    for (int i = 1 ; i <= n ; i ++ ) {
        cin >> w[i];
        w[i + n] = w[i];

    }
    for (int i = 1 ; i <= n * 2 ; i ++ ) {
        sum[i] = sum[i - 1] + w[i];
        f[i][i] = 0 , g[i][i] = 0;   
    }
    for (int len = 2 ; len <= 2 * n ; len ++ ) 
        for (int l = 1 ; l <= 2 * n - len + 1 ; l ++ ) {
            int r = l + len - 1;
            for (int k = l ; k < r;  k ++ ) {
                f[l][r] = min(f[l][r] , f[l][k] + f[k + 1][r] + sum[r] - sum[l - 1]);
                g[l][r] = max(g[l][r] , g[l][k] + g[k + 1][r] + sum[r] - sum[l - 1]);
            }
        }
    int minV = 0x3f3f3f , maxV = -0x3f3f3f3f;
    for (int i = 1 ; i <= n ; i ++ ) {
        minV = min(f[i][i + n - 1] , minV);
        maxV = max(g[i][i + n - 1] , maxV);
    }
    cout << minV << endl;
    cout << maxV << endl;


    return 0;
}