模拟赛被卡常了。

赛时认为记忆化搜索非常自然，我们考虑搜索第

now

个房间放小于

maxm

个生物的答案。

临界条件肯定是

now = n

，这时候直接返回

maxm-1

就可以。

首先若

a_{now} \ge maxm

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

CPP

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

其次就是

a_{now} < maxm

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

CPP

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

CPP

#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;
}

题解：P6715 [CCO 2018] Fun Palace

文章操作

code

相关推荐

评论

题解：P6715 [CCO 2018] Fun Palace