区间DP经典石子合并

#include
using namespace std;
typedef long long ll;
const int inf=1<<30;
const int maxn=210;
const double pi=acos(-1);
const int mod=1e9+7;
int a[maxn],sum[maxn];
int dp1[maxn][maxn],dp2[maxn][maxn];
int d(int x,int y){
    return sum[y]-sum[x-1];
}
int main(){
    int n;scanf("%d",&n);
    //fill((int *)dp2,(int *)dp2+maxn*maxn,inf);
    for(int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    a[i+n]=a[i];
    sum[i]=sum[i-1]+a[i];
    }
    for(int i=n+1;i<=2*n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    for(int len=2;len<=n;len++){
        for(int l=1;(l+len-1)<=2*n;l++){
            int r=l+len-1;
            dp2[l][r]=inf; 
            for(int k=l;k//注意k是比r小的，因为是左边是l到k，右边是k+1-r 
                dp1[l][r]=max(dp1[l][r],dp1[l][k]+dp1[k+1][r]+d(l,r));
                dp2[l][r]=min(dp2[l][r],dp2[l][k]+dp2[k+1][r]+d(l,r));
            }
        }
    }
    int mx=0,mn=inf;
    for(int i=1;i<=n;i++){
        mx=max(mx,dp1[i][i+n-1]);
        mn=min(mn,dp2[i][i+n-1]);
    }
    cout<endl;
    return 0;
}