题解：P6715 [CCO 2018] Fun Palace

许多 · 2025-10-21 08:08:25 · 题解

模拟赛被卡常了。

赛时认为记忆化搜索非常自然，我们考虑搜索第 now 个房间放小于 maxm 个生物的答案。

临界条件肯定是 now = n，这时候直接返回 maxm-1 就可以。

首先若 a_{now} \ge maxm ，这种情况门无论如何不能从左边打开。由于生物可以来回走，太过麻烦，所以我又分成了两种小情况，即门可不可以从右边打开，如果可以的话，我们不妨让当前房间里的生物全部移动到右边，计算答案。

if(a[now]>=maxm)ans=max(maxm-1+dfs(now+1,b[now]),dfs(now+1,b[now]+maxm));

其次就是 a_{now} < maxm，这个分成三种情况计算：门无法被打开，门只可以从左边被打开，门可以从右边打开(这部分又分成是否可以通过移动使得门可以从左边打开)。

else ans=max(max(a[now]-1+dfs(now+1,b[now]),a[now]+dfs(now+1,min(b[now],maxm-a[now]))),dfs(now+1,max(maxm,b[now]+a[now])));  

code

#include<bits/stdc++.h>
#define N 2020
#define M 40020
using namespace std;
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*10+(ch-'0'),ch=getchar();
    return x*f;
}
int n,m,Mnow;
int a[N],b[N];
int f[N][M];
int dfs(int now,int maxm){
    if(f[now][maxm])return f[now][maxm];
    int ans=0;
    if(now==n){return f[now][maxm]=maxm-1;}
    if(a[now]>=maxm)ans=max(maxm-1+dfs(now+1,b[now]),dfs(now+1,b[now]+maxm));
    else ans=max(max(a[now]-1+dfs(now+1,b[now]),a[now]+dfs(now+1,min(b[now],maxm-a[now]))),dfs(now+1,max(maxm,b[now]+a[now])));
    return f[now][maxm]=ans;                                                                
}
int main(){
    n=read();m=Mnow=read();
    for(int i=1;i<n;i++)
        a[i]=read(),b[i]=read(),Mnow=max(Mnow,max(a[i],b[i]));
    printf("%d\n",dfs(1,m));
    return 0;
}