题解

“石子围成圈”，"相邻两堆石子"都要注意
思路：用隔板法，遍历i~j里每个点，视为隔板(k)，用dp记录区域内的最大或最小得分，比较隔板左右(dp[i][k]和dp[k+1][j])加区域总值的和与原值大小，再存入dp[i][j]
递推公式：
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

#include<iostream>
using namespace std;
const int Max=2147483647;
int n,a[110];//见题目
int sum[210];//用前缀和方便我们区域求和
int dp1[210][210],dp2[210][210];//dp[i][j]表示i~j范围内的最值
int MAX=0,MIN=Max;//答案
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=n+1;i<=2*n;i++)//因为围成圈，所以sum要加到2n
        sum[i]=sum[i-1]+a[i-n];
    for(int l=2;l<=n;l++){//需要求的区间的长度
        for(int i=1,j=l;j<=2*n;i++,j++){//区间范围
            dp1[i][j]=Max;//赋初值，方便比较
            dp2[i][j]=0;
            for(int k=i;k<j;k++){//遍历每个隔板
                dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]);//递推
                dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]);
            }
            if(l==n){
                MIN=min(MIN,dp1[i][j]);
                MAX=max(MAX,dp2[i][j]);
            }
        }
    }
    cout<<MIN<<"\n";
    cout<<MAX;
    return 0;
}