Description
题意简述来自Gypsophila。
你现在要怼 $m$ 个大佬,第 $i$ 个大佬的自信值是 $C_i$ 。每次怼大佬之前,你的自信值是 $mc$,等级 $L=0$,嘲讽值 $F = 1$。对于每一个大佬,你都有 $n$ 天时间来怼大佬。无论哪个大佬,他们都会在第 $i$ 天使你的的自信值下降 $a_i$ 如果你的自信值为负数,那么你失败了。在第 $i$ 天,你可以干一下事情中的恰好一件:
- 使得大佬自信值下降 $1$
- 使得自己的自信值增加 $w_i$
- 把自己的等级 $+1$
- 把自己的 $F$ 乘上 $L$
- 怼大佬,使得大佬的自信值下降 $F$,之后$L=0$ ,$F=1$(该操作最多使用 2 次)
- 如果中途大佬自信值为负数,你失败了。若大佬自信值恰好为 $0$ ,则你成功了。
对于每个大佬求你能否成功。
$1\leq n,mc\leq 100,1\leq m\leq 20,1\leq a_i,w_i\leq mc,1\leq C_i\leq 10^8$
Solution
显然我们要做的就是在活下来的情况下,尽可能地把大佬砍到 0。首先我们需要知道最多能空出几天来砍大佬。
设 $f_{i,j}$ 表示前 $i$ 天空 $j$ 天时自己的最大血量。初始 $f_{0,0}=mc$。可以 $O(n^2)$ DP 算出答案,记为 $maxd$。
那么我们考虑如果在 $maxd$ 天内砍大佬。
- 不用“怼大佬”。显然,若是 $C_i\leq maxd$,可以直接把大佬砍死;
- 用一次“怼大佬”,我们记怼大佬用的时间(准备时间(累加 $L$ 和累乘 $F$ 的时间)+怼大佬的那天)为 $d$,造成的伤害为 $f$。那么由于不能把大佬砍成负,要满足 $f\leq C_i$,又要把大佬砍到 0,因此 $f+maxd-d\geq C_i$;
- 用两次“怼大佬”,我们记怼大佬用的时间分别为为 $d_1,d_2$,造成的伤害为 $f_1,f_2$。那么要满足 $f_1+f_2\leq C_i$ 以及 $f_1+f_2+maxd-d_1-d_2\geq C_i$。
考虑如何找到所有的 $(d,f)$,做法是直接暴力搜索,注意搜索的时候判重以及一些最优性减枝。
对于上述第 3 个情况,我们不能去暴力枚举。但是实际上对于每个 $f_1$ 我们要找的就是最大的 $f_2$ 使得 $f_1+f_2\leq C_i$。这样我们将所有方案排序后用双指针扫就好了。
Code
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
const int N = 105, C = 1e8;
struct piii {
int d, l, f;
piii (int _d = 0, int _l = 0, int _f = 0) {
d = _d, l = _l, f = _f;
}
bool operator < (const piii &b) const {
if (d == b.d && f == b.f) return l < b.l;
if (f == b.f) return d > b.d;
return f < b.f;
}
bool operator == (const piii &b) const {
return d == b.d && l == b.l && f == b.f;
}
};
int n, m, mc, a[N], w[N], f[N][N], c;
int maxd, head, tail;
map<pii, bool> mp;
piii q[N*N*N<<2], t;
pii v;
void bfs() {
t = piii(1, 0, 1);
q[head = tail = 1] = t;
mp[pii(0, 1)] = 1;
while (head <= tail) {
t = q[head++];
if (t.d >= maxd) continue;
if (mp[v = pii(t.l+1, t.f)] == 0) {
mp[v] = 1;
q[++tail] = piii(t.d+1, t.l+1, t.f);
}
if (t.l > 1 && 1ll*t.f*t.l <= C && mp[v = pii(t.l, t.f*t.l)] == 0) {
mp[v] = 1;
q[++tail] = piii(t.d+1, t.l, t.f*t.l);
}
}
}
int main() {
scanf("%d%d%dd", &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]);
memset(f, -1, sizeof(f));
f[0][0] = mc;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= i; j++) {
if (f[i-1][j]-a[i] >= 0)
f[i][j] = max(min(f[i-1][j]-a[i]+w[i], mc), f[i][j]);
if (j && f[i-1][j-1]-a[i] >= 0)
f[i][j] = max(f[i-1][j-1]-a[i], f[i][j]);
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= i; j++)
if (f[i][j] >= 0) maxd = max(maxd, j);
bfs();
sort(q+1, q+tail+1);
for (int i = 1; i <= m; i++) {
scanf("%d", &c); int r;
if (c <= maxd) {
puts("1"); continue;
}
for (int i = 1; i <= tail; i++)
if (q[i].f <= c && q[i].f+maxd-q[i].d >= c) {
puts("1"); goto qwq;
}
r = tail;
for (int l = 1; l <= r; l++) {
while (l <= r && q[l].f+q[r].f > c) --r;
if (l <= r && q[l].f+q[r].f+maxd-q[l].d-q[r].d >= c) {
puts("1"); goto qwq;
}
}
puts("0");
qwq: 1;
}
return 0;
}