Codeforces 796E - Exam Cheating（dp）

当被数据结构搞自闭的 tzc 信心满满地点开一道 *2400 的 dp 题时……

却发现自己不会做？！

这足以证明蒟蒻 dp 之菜/dk/dk/wq/wq

设 \(a_i=[\text{第一个人会做第}\ i\ \text{题}]\)，\(b_i=[\text{第二个人会做第}\ i\ \text{题}]\)

考虑 \(dp\)，\(dp_{i,j,x,y}\) 表示现在已经考虑到了第 \(i\) 个人，现在已经消耗了 \(j\) 次偷看的机会，此次向左边的人的偷看机会已经向左边的人偷看 \(x\) 题，此次向左边的人的偷看机会已经向左边的人偷看 \(y\) 题，所能做出的最多题数。如果 \(x=k\) 表示在不消耗新的偷看机会的情况下不能再偷看第一个人的试卷，\(y=k\) 也同理。

分两种情况转移：

不消耗新的偷看机会，即从 \(dp[i][j][x][y]\) 转移到 \(dp[i+1][j][\min(x+1,k)][\min(y+1,k)]\)，此时能多做出一道题当且仅当 \((a_{i+1}\land x+1\leq k)\lor (b_{i+1}\land y+1\leq k)\)，即 \(dp[i+1][j][\min(x+1,k)][\min(y+1,k)]\leftarrow dp[i][j][x][y]+(a_{i+1}\land x+1\leq k)\lor (b_{i+1}\land y+1\leq k)\)
消耗新的偷看机会。还是分两种情况，一是偷看第一个人的试卷，即 \(dp[i+1][j+1][1][\min(y+1,k)]\leftarrow dp[i][j][x][y]+a[i+1]\)，第二种是偷看右边人的试卷，即 \(dp[i+1][j+1][\min(x+1,k)][1]\leftarrow dp[i][j][x][y]+b[i+1]\)。

最终答案即为 \(\max dp[n][j][x][y]\)。

这样 DP 时间复杂度为 \(npk^2\)，会炸。考虑优化，感性理解一下可知当 \(p\) 比较大的时可以选择将两个人的每道题的答案看完，这样答案即为 \(a_i\lor b_i=1\) 的 \(i\) 的个数。随便算一下就知道这样的 \(p\) 的临界值为 \(2\lceil\dfrac{n}{k}\rceil\)，也就是说你只需对 \(p\leq 2\lceil\dfrac{n}{k}\rceil\) 的情况跑一遍上述 DP 即可。时间复杂度也随之降到了 \(n^2k\)。

注意滚动数组优化，否则会 MLE。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

typedef unsigned int u32;

typedef unsigned long long u64;

namespace fastio{

	#define FILE_SIZE 1<<23

	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;

	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}

	inline void putc(char x){(*p3++=x);}

	template<typename T> void read(T &x){

		x=0;char c=getchar();T neg=0;

		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();

		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

		if(neg) x=(~x)+1;

	}

	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}

	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}

	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}

}

const int MAXN=1e3;

const int MAXK=50;

int n,n1,n2,p,k,dp[2][MAXN+5][MAXK+3][MAXK+3];

int isa[MAXN+5],isb[MAXN+5];

int main(){

	scanf("%d%d%d",&n,&p,&k);

	scanf("%d",&n1);for(int i=1,x;i<=n1;i++) scanf("%d",&x),isa[x]=1;

	scanf("%d",&n2);for(int i=1,x;i<=n2;i++) scanf("%d",&x),isb[x]=1;

	if(p>=(n+k-1)/k*2){

		int ret=0;

		for(int i=1;i<=n;i++) ret+=isa[i]|isb[i];

		printf("%d\n",ret);return 0;

	}

	int pre=0,cur=1;memset(dp[pre],192,sizeof(dp[pre]));

	dp[pre][0][k][k]=0;

	for(int i=1;i<=n;i++){

		memset(dp[cur],192,sizeof(dp[cur]));

		for(int j=0;j<=p;j++){

			for(int x=1;x<=k;x++) for(int y=1;y<=k;y++){

				chkmax(dp[cur][j][min(x+1,k)][min(y+1,k)],dp[pre][j][x][y]+((isa[i]&&x<k)||(isb[i]&&y<k)));

				if(j<p){

					if(isa[i]) chkmax(dp[cur][j+1][1][min(y+1,k)],dp[pre][j][x][y]+1);

					if(isb[i]) chkmax(dp[cur][j+1][min(x+1,k)][1],dp[pre][j][x][y]+1);

				}

			}

		} pre^=cur^=pre^=cur;

	} int ans=0;

	for(int j=0;j<=p;j++) for(int x=1;x<=k;x++) for(int y=1;y<=k;y++)

		chkmax(ans,dp[pre][j][x][y]);

	printf("%d\n",ans);

	return 0;

}

巴特西

Codeforces 796E - Exam Cheating（dp）

最新文章

热门文章