题解 AT2433 【ケーキの切り分け２ (Cake 2)】

君のNOIP。 · 2020-03-20 20:18:58 · 题解

很明显のdp

闲扯：

• 最后一定要换行！不然#1就WA

• 我花了1h找转移方程，结果却又花半天调试找bug，已自闭。

• 绝对是很神奇のdp，但转移方程也就两行。

• 一定要注意细节，不要和我一样。

• 那么久了才十几个人做过，（所以我才能做第一篇题解

正片开始：

数据范围：

• N \le 2000
• a_i \le 10^9

结论：

• 十有八九是 dp 了。

• 不开 long long 见祖宗。

基本思路：

• 设先拿の人为 A，后拿の人为 B。

• 首先状态很好想： dp_{i,j} 表示在区间 [ i , j ] 上 A 能拿の最大值。

• 由于这是一个环，我们只需要开两倍数组。

• 答案很显然是 \max dp_{i,i+N-1} , i\in [ 1 , N ]

初始化:

• a_0 = a_N

重点！

转移方程：

• 只有当 j-i 为偶时，A才会取，所以要分类讨论。

• 当 j-i 为偶：很明显 dp_{i,j} 只能由 dp_{i+1,j} と　dp_{i,j-1} 得来。

• 所以 dp_{i,j} = \max (dp_{i+1,j} + a_i , dp_{i,j-1} + a_j )

• 当 j-i 为奇：很明显 dp_{i,j} 还是只能由 dp_{i+1,j} と　dp_{i,j-1} 得来。

• 但是（重难点）！

• 如果可供选择的蛋糕有多个， B 酱会选择最大的一个。

• 所以若 dp_{i,j} 由 dp_{i+1,j} 得来，则需满足 a_i > a_{j+1}

• 同理，若 dp_{i,j} 由 dp_{i,j-1} 得来，则需满足 a_j > a_{i-1}

• 若同时满足取 max，否则为 -1 即可。

细节：

• 由于 dp_{i,j} 可能由 dp_{i+1,j} と　dp_{i,j-1} 得来（可能会从左右两边拓展），我们便不能简单枚举 i と j 。

• 所以我们需要枚举 k （即区间长度 -1 ）， 然后枚举 i ， 使 j = i+ k 即可。

• 当 k = n-1 ，且 j-i 为奇，只剩下一个肯定能取，不用比较大小了。

完整代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define G() Cr=getchar()
#define LL long long
LL Xr;char Cr;
inline LL rd(){   //读入优化
    Xr=0,G();
    while(Cr<'0'||Cr>'9')G();
    while(Cr>='0'&&Cr<='9')Xr=(Xr<<3)+(Xr<<1)+Cr-'0',G();
    return Xr;
}
#define MAX_N 4005
int n;
LL va[MAX_N],dp[MAX_N][MAX_N],ans;

LL min(LL x,LL y){return x>y?y:x;}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)va[i]=rd(),va[i+n]=va[i]; 
    va[0]=va[n];

    for(int i=1;i<=n;i++)dp[i][i]=dp[i+n][i+n]=va[i];

    for(int k=1;k<n;k++){
        for(int i=1;i+k <= n<<1 ;i++){
            int j=i+k;
            if(k & 1)
                dp[i][j]=max( (va[j]>va[i-1]||k==n-1)?dp[i][j-1]:-1,
                (va[i]>va[j+1]||k==n-1)?dp[i+1][j]:-1 );
            else
                dp[i][j]=max(dp[i+1][j]+va[i],dp[i][j-1]+va[j]);
        }
    }

    for(int i=1;i<=n;i++)ans=max(dp[i][i+n-1],ans);
    cout<<ans<<endl;    
}

完结撒花！

可惜如此冷门の题（3.20了，我还是2020年第一个做的）大概不会有几个人能看到私の题解了。

でも，不能放任无题解のAT题目不管啊。