[区间dp]石子合并（洛谷P1880）

传送门

石子合并

AC代码

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

int a[210], f[210][210], sum[210], f2[210][210];

int main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[n+i] = a[i];
        sum[i] = sum[i-1] + a[i];
    }
    
    for(int i = n+1; i <= n+n; i++){
        sum[i] = sum[i-1] + a[i];
    }
    
    for(int len = 1; len <= n; len++){
        for(int i = 1, j = i + len; (j <= n+n) && i <= n+n; i++ , j = i+len){
            f2[i][j] = 0x3f3f3f;
            for(int k = i; k < j; k++){
            //  cout << sum[j] - sum[i-1] << endl;
                f[i][j] = max(f[i][j],  f[i][k]+f[k+1][j]+sum[j] - sum[i-1]);
                f2[i][j] = min(f2[i][j], f2[i][k]+f2[k+1][j]+ sum[j] - sum[i-1]);
            }
        }
    }
    
    int maxn = -1;
    for(int i = 1; i <= n; i++){
        maxn = max(maxn, f[i][i+n-1]);
    }
    int minn = 0x3f3f3f;
    for(int i = 1; i <= n; i++){
        minn = min(minn, f2[i][i+n-1]);
    }
    cout << minn << endl;
    cout << maxn << endl;
    return 0;
}