网站链接: element-ui dtcms
当前位置: 首页 > 技术博文  > 技术博文

模拟赛2021.4.4 密室逃脱(escape)——DP

2021/4/4 19:47:58 人评论

题目描述 题解 看了题目首选DP,设 表示第 i 个房间的人数最多可达 j 人时,前 i 个房间人数最多是多少。 当我们向后转移时,根据 j 的大小可以分三种情况讨论: ,那么 i 房间的人无法主动往后走,所以可以…

题目描述

题解

看了题目首选DP,设 dp[i][j] 表示第 i 个房间的人数最多可达 j 人时,前 i 个房间人数最多是多少。

当我们向后转移时,根据 j 的大小可以分三种情况讨论:

  1. 0\leq j<a[i],那么 i 房间的人无法主动往后走,所以可以从 dp[i][0~a[i]-1] 中取最大值 g ,转移至dp[i+1][k]=max(dp[i+1][k],g+k),0 \leq k <b[i]。若 k\geq b[i],那么当第 i 个房间人最多为 j 时,第 i+1 个房间人数只能为 b[i] ,否则第 i 个房间人数肯定还能增长,此时,第 i+1 个房间人数最多就为 j+b[i] ,因为这 j 个人可以全部跑到第 i+1 个房间,所以有dp[i+1][j+b[i]]=max(dp[i+1][j+b[i]],dp[i][j]+b[i])
  2. a[i]\leq j < a[i]+b[i],此时最多有 j-a[i] 个人可以在 i 、i+1 间自由往来,所以第 i+1 个房间最多有 j-a[i] 个人,即dp[i+1][j-a[i]]=max(dp[i+1][j-a[i]],dp[i][j])
  3. j \geq a[i]+b[i],此时这 j 个人可以全部在 i 、i+1 间自由往来,所以第 i+1 个房间最多有 j 个人,即dp[i+1][j]=max(dp[i+1][j],dp[i][j])

通过第三条我们可以发现,当人数\geq max(a[i]+b[i])时,所有人都可以在所有房间自由往来,此时若不小于 m 个人则不合法,所以第二维的 j 最大为max(m,a[i]+b[i])\leq 20000

总复杂度O(2nm)

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
#define uns unsigned
#define MAXN 100005
#define INF 0x3f3f3f3f
using namespace std;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+s-'0',s=getchar();
	return f?x:-x;
}
int n,m,a[1005],b[1005],ans;
int dp[1005][20015],len[1005];
signed main()
{
//	freopen("escape.in","r",stdin);
//	freopen("escape.out","w",stdout);
	n=read(),m=read();
	for(int i=1;i<n;i++)a[i]=read(),b[i]=read();
	for(int i=1;i<m;i++)dp[1][i]=i;
	len[1]=m-1;
	for(int i=1;i<n;i++){
		int g=0;
		for(int j=0;j<=len[i]&&j<a[i];j++)g=max(g,dp[i][j]);
		for(int j=0;j<b[i];j++)dp[i+1][j]=max(dp[i+1][j],g+j);
		len[i+1]=max(len[i+1],b[i]-1);
		for(int j=0;j<=len[i]&&j<a[i];j++)
			dp[i+1][b[i]+j]=max(dp[i+1][b[i]+j],dp[i][j]+b[i]),len[i+1]=max(len[i+1],b[i]+j);
		for(int j=a[i];j<=len[i];j++){
			if(j-a[i]<b[i])
				dp[i+1][j-a[i]]=max(dp[i+1][j-a[i]],dp[i][j]),len[i+1]=max(len[i+1],j-a[i]);
			else dp[i+1][j]=max(dp[i+1][j],dp[i][j]),len[i+1]=max(len[i+1],j);
		}
	}
	for(int i=0;i<=len[n];i++)ans=max(ans,dp[n][i]);
	printf("%d\n",ans);
	return 0;
}

 

相关资讯

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?