夏晓光(loveJY)的博客

好难啊

首先我们应该能观察到我刷水题和我怼大佬两件事是可以分开的,也就是说我们可以先写一个dp处理我前i天刷水题的最少次数(也就是留给其他操作的最多次数),再写一个dp处理之后操作?

会发现我们不太行,因为我们有两次怼大佬,如果只有一次的话我们就可以搜索出来所有的最少操作打出的伤害了

就是说写一个类似于bfs的东西,然后把(使用天数,造成伤害)所有的这样的pair搞出来,这样我们就能得知只使用一次怼大佬操作的答案,就是使用一个pair,搜索的状态....这个不用说了吧?

把上述pair按照嘲讽值排序,由于这样的pair可能高达$2^20$个,我们只好思考能不能用双指针类似的思想来快速找到两个合并得到两次操作的答案

怎么合并呢?

首先我们有使用天数要合并,显然使用的天数不能超过第一个DP得出的怼大佬次数的最大值,其次我们造成的伤害由于题目的要求不能超过大佬的$C_i$如果超过就会导致一击打成负数然后被暴虐了.....

紧接着,我们要有机会把大佬的自信打成0,所以我们剩下的天数(maxd-d1-d2)还要大于大佬剩下的(C_i-f1-f2),这样我们才能打爆他

综上,我们天数和一定,所以一维单增同时另一维单减,再每次减少的同时判断能不能打死即可,双指针了

code:

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp(x,y) (make_pair(x,y))
const int MAXN = 120;
const int MAXT = 1e6 + 7;
int n, m, mc, T, mx;
int a[MAXN], w[MAXN], c[MAXN];
int dp[MAXN][MAXN];
int maxd;
inline int chkmax(int &x, int y) {
	x = max(x, y);
	return x;
}

map<pair<int, int>, int> mp;
struct nod {
	int i, F, L;
	nod(int x = 0, int y = 0, int z = 0): i(x), F(y), L(z) {};
};
pair<int, int> zt[MAXT];

queue<nod> Q;
inline void search() {
	queue<nod> Q;
	Q.push((nod) {
		1, 1, 0
	});
	while(!Q.empty()) {
		nod u = Q.front();
		Q.pop();
		if(u.i == maxd)continue;
		// printf("node:%d %d %d\n", u.i, u.F, u.L);
		Q.push((nod) {
			u.i + 1, u.F, u.L + 1
		});
		if(u.L > 1 && 1ll * u.F * u.L <= 1ll * mx &&
				(mp.find(mkp(u.F * u.L, u.i + 1)) == mp.end())) {
			Q.push((nod) {
				u.i + 1, u.F *u.L, u.L
			});
			zt[++T] = mkp(u.L * u.F, u.i + 1);
			mp[mkp(u.F * u.L, u.i + 1)] = 1;
		}
	}
	return ;
}

int main() {
	scanf("%d%d%d", &n, &m, &mc);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &w[i]);
	}
	for(int i = 1; i <= m; ++i) {
		scanf("%d", &c[i]);
		mx = max(mx, c[i]);
	}
	// for(int p = 1; p <= m; ++p) {
	memset(dp, -0x3f, sizeof(dp));
	dp[0][mc] = 0;//初始状态?
	for(int i = 0; i < n; ++i) {
		for(int k = 0; k <= mc; ++k) {
			if(k >= a[i + 1]) {
				chkmax(dp[i + 1][min(k - a[i + 1] + w[i + 1], mc)], dp[i][k]); //刷题
				chkmax(dp[i + 1][k - a[i + 1]], dp[i][k] + 1);//不刷题
			}
			// printf("%d %d %d?%d %d \n", i, k, dp[i][k], dp[i + 1][k - a[i + 1] + w[i + 1]], dp[i + 1][k - a[i + 1]]);
		}
	}
	for(int i = 1; i <= n; ++i)
		for(int k = 0; k <= mc; ++k) {
			chkmax(maxd, dp[i][k]);
		}
	search();
	// printf("%d %d\n", p, maxd[p]);
	// }
	sort(zt + 1, zt + T + 1);
	for(int i = 1; i <= m; ++i) {
		if(c[i] <= maxd) {//如果小于最大天数直接反死
			puts("1");
			continue;
		}
		bool fl = 0;
		int mm = 1e9;
		for(int j = T, k = 1; j; --j) {
			while(k < T && zt[k].fi + zt[j].fi <= c[i])//伤害和小于
				mm = min(mm, zt[k].se - zt[k].fi),//最小化这个才能满足下面的式子
				++k;
			if(mm + c[i] - zt[j].fi <= maxd - zt[j].se) {//拆开mm可以得到c_i-fj-fi<=maxd-di-dj
				fl = 1;
				break;
			}
			if(zt[j].fi <= c[i] && c[i] - zt[j].fi <= maxd - zt[j].se) {//如果我们一击就能打死
				fl = 1;
				break;
			}
		}
		fl ? puts("1") : puts("0");
	}
	return 0;
}