P1880 [NOI1995] 石子合并

P1880 [NOI1995] 石子合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

本题重要的是是个圆。

圆的通常思维，是把圆拆成两条链

这样子 n 变成 2*n（区间dp模板题）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back   //vector函数
#define popb pop_back  //vector函数
#define fi first
#define se second
const int N=210;
//const int M=;
const int inf=0x3f3f3f3f;     //一般为int赋最大值,不用于memset中
//const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中
int T,n,a[N],sum[N];
int dp[2][N][N];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main()
{
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) a[i]=read(),sum[i]=sum[i-1]+a[i];
    for(int i=n+1;i<=2*n;i++) a[i]=a[i-n],sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=2*n;i++)
        for(int j=1;j<=2*n;j++) dp[0][i][j]=inf;
    for(int i=1;i<=2*n;i++) dp[0][i][1]=0;
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=2*n;i++)
            for(int j=i;j<=i+len-2;j++)
            {
                dp[0][i][len]=min(dp[0][i][len],dp[0][i][j-i+1]+dp[0][j+1][i+len-j-1]+sum[i+len-1]-sum[i-1]);
                dp[1][i][len]=max(dp[1][i][len],dp[1][i][j-i+1]+dp[1][j+1][i+len-j-1]+sum[i+len-1]-sum[i-1]);
            }
    int ans1=inf,ans2=0;
    for(int i=1;i<=n;i++) ans1=min(ans1,dp[0][i][n]),ans2=max(ans2,dp[1][i][n]);
    printf("%d\n%d",ans1,ans2);
    return 0;
}