NC50493 石子合并

分析

由于石子摆在圆形操场的四周，因此 $n$ 堆石子会摆放成一个环，于是不妨将 $n$ 堆石子复制一份，使得 $a_i=a_{i+n}$ 。
定义 $dp_{min}[i][j]$ 为合并区间 $[i,j]$ 内石子获得的最小得分，有状态转移方程 $dp_{min}[i][j]=\min\limits_{i\le k<j}(dp_{min}[i][k]+dp_{min}[k+1][j]+count(i,j))$ 。同理，定义 $dp_{max}[i][j]$ 为合并区间 $[i,j]$ 内石子获得的最大得分，有状态转移方程 $dp_{max}[i][j]=\max\limits_{i\le k<j}(dp_{max}[i][k]+dp_{max}[k+1][j]+count(i,j))$ 。所求即为 $\min\limits_{1\le i\le n-1}dp_{min}[i][i+n]$ 和 $\max\limits_{1\le i\le n-1} dp_{max}[i][i+n]$ 。

代码

#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#define N 302
using namespace std;
int dp_min[N][N];
int dp_max[N][N];
int n;
int sum[N];
int a[N];
int main()
{
    //初始化
    memset(dp_min,0x3f,sizeof(dp_min));
    memset(dp_max,0,sizeof(dp_max));
    int i,j,k;
    cin>>n;
    for(i=1;i<=n;i++) scanf("%d",a+i);
    for(i=n+1;i<=2*n;i++) a[i]=a[i-n];
    //O(1)获得count(i,j)
    for(i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
    for(j=1;j<=2*n;j++)//右边界
    {
        for(i=j;i>=1;i--)//左边界
        {
            if(i==j) dp_min[i][j]=dp_max[i][j]=0;
            for(k=i;k<j;k++)//分界点
            {
                dp_min[i][j]=min(dp_min[i][k]+dp_min[k+1][j]+sum[j]-sum[i-1],dp_min[i][j]);
                dp_max[i][j]=max(dp_max[i][k]+dp_max[k+1][j]+sum[j]-sum[i-1],dp_max[i][j]);
            }
        }
    }
    int ans_min=0x3f3f3f3f,ans_max=-1;
    for(i=1;i<=n-1;i++)
    {
        ans_min=min(ans_min,dp_min[i][i+n-1]);
        ans_max=max(ans_max,dp_max[i][i+n-1]);
    }
    cout<<ans_min<<endl<<ans_max<<endl;
    return 0;
}