AT_joi2015ho_b ケーキの切り分け２ (Cake 2)

MYJ_aiie · 2023-11-12 13:27:11 · 题解

题目

思路：

区间DP，用 f[i][j] 表示选完 i 到 j 块的最大值。
因为 IOI酱 默认选能选的中最大的，所以不用特意去记录 IOI 酱。
我们发现 i 到 j 的区间可以由 3 种情况推过来，分别是 f[i][j-2],f[i+1][j-1],f[i+2][j]
每选一次，相当于 JOI 和 IOI 都选一次，所以长度为偶数。
同时考虑一个问题，那就是 IOI 选的最大值可能不在 i 到 j 的区间里，这就需要特殊判断了。举个例子， f[i][j-2] 到 f[i][j] 的转移中，当我们选择了 a[j-1] 而 a[j]<a[i-1] ，这个时候 IOI 酱应该会选 a[i-1] 而不是 a[j] 。

注意：因为是圆形所以要要复制一遍放在后面。

code:

#include<bits/stdc++.h>
using namespace std;
const int N=4005;
long long n;
long long a[N*2];
long long f[N][N];
int main()
{
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i+n]=a[i];
    }
    a[0]=a[n];
    a[n*2+1]=a[0];
    for(int l=2;l<=n;l+=2)
    {
        for(int i=1;i<=n;i++)
        {
            int j=i+l-1;

            long long t1,t2,t3;
            t1=t2=t3=0;
            if(a[j+1]<=a[i]) 
                t1=f[i+2][j]+a[i+1];
            if(a[j+1]<=a[i])
                t2=f[i+1][j-1]+a[j];
            if(a[i-1]<=a[j]) 
                t2=max(t2,f[i+1][j-1]+a[i]);
            if(a[i-1]<=a[j])
                t3=f[i][j-2]+a[j-1];
            f[i][j]=max(t1,max(t2,t3));
            if(j+n<=2*n) f[i+n][j+n]=f[i][j];
        //  cout<<i<<" "<<j<<" "<<f[i][j]<<" "<<t1<<" "<<t2<<" "<<t3<<endl;
        }
    }
    long long ans=0;
    if(n%2==0)
    {
        for(long long i=1;i<=n;i++)
        {
            ans=max(ans,f[i][i+n-1]);
        }
    }
    if(n%2==1)
    {
        for(long long i=1;i<=n;i++)
        {
            ans=max(ans,f[i][i+n-2]+a[i+n-1]);
        }
    }
    printf("%lld",ans);
    return 0;
}