题目大意
「AHOI / HNOI 2017」大佬（Luogu 3724）
有 $q$ 个大佬，你要和他们一一对决。对决分 $n$ 天，你的初始自信值为 $m$，大佬的初始自信值为 $C$。如果某一天你将大佬的自信值恰好减到 $0$，并且在这天之前你的自信值都不小于 $0$，那么你就获胜了。
一开始，你的等级 $L$ 为 $0$，讽刺能力 $F$ 为 $1$。在第 $i$ 天，大佬会将你的自信值减少 $a_i$，然后你可以进行下列操作中的一种：
- 还一句嘴，使大佬的自信值减去 $1$。
- 做一天的水题，使自己的自信值 $+ w_i$。注意当前自信值修改后要对初始生命值取 $\min$。
- 使自己的等级 $L$ 增加 $1$。
- 使自己的讽刺能力 $F$ 乘上自己的等级 $L$。
- 怼大佬，使大佬的自信值减少 $F$。之后 $L, F$ 都回到初始值。这种操作只能进行不超过 $2$ 次。
问对于每个大佬，你是否能够战胜他。
数据范围：$n, m \le 100, q \le 20, C \le 10^8$。
思路分析
首先我们发现获胜的条件可以拆成：保证自己活着，并且在 $n$ 天内将大佬的自信值扣到 $0$。我们先做一个 DP 来看看我们最多可以花多少天来怼大佬。值得注意的是，我们不必需要用完所有的天数，所以我们在任何一天停止都是合法的。下面我们将 $n$ 变为求出的有效天数。
接下来我们考虑如何有效地怼大佬。我们一共可以怼他 $0, 1, 2$ 次。预先进行一次 BFS，求出所有的形如 $(F, D)$ 的有序数对，表示我们使用 $D$ 天可以将讽刺能力增加到 $F$。我们需要用 map 记录访问过的 $(L, F)$ 数对来避免重复访问。暴力 BFS 的规模太大，但是我们发现我们只需要 BFS 到第 $32$ 层即可退出。
之后，对于每一个大佬，我们容易处理出怼他 $0$ 或 $1$ 次是否会成功，接下来考虑怼他两次是否会成功。由于我们要求 $F_a + F_b \le C$，所以使用 two - pointers 的技巧，对于每个合法的对看 $D_a + D_b + C - F_a - F_b \le n$ 是否成立即可。这样，我们已经解决了这个问题。
代码实现
1 | |
2 | |
3 | |
4 | |
5 | using namespace std; |
6 | |
7 | const int maxn = 100, maxm = 1e7, inf = 1e8 + 1; |
8 | int n, q, m, a[maxn + 3], w[maxn + 3], dp[maxn + 3][maxn + 3]; |
9 | int M, c[25], h, t, Qd[maxm + 3], Ql[maxm + 3], Qf[maxm + 3]; |
10 | map<pair<int, int>, bool> vis; |
11 | map<int, int> mp; |
12 | int cnt, D[maxm + 3], F[maxm + 3]; |
13 | |
14 | void upd_max(int &x, int y) { |
15 | x < y ? x = y : 0; |
16 | } |
17 | |
18 | void upd_min(int &x, int y) { |
19 | x > y ? x = y : 0; |
20 | } |
21 | |
22 | void prework() { |
23 | for (int i = 1; i <= n; i++) { |
24 | for (int j = a[i]; j <= m; j++) { |
25 | dp[i][j - a[i]] = max(dp[i][j - a[i]], dp[i - 1][j] + 1); |
26 | upd_max(dp[i][min(m, j - a[i] + w[i])], dp[i - 1][j]); |
27 | } |
28 | } |
29 | int x = 0; |
30 | for (int i = 1; i <= n; i++) { |
31 | for (int j = 0; j <= m; j++) { |
32 | upd_max(x, dp[i][j]); |
33 | } |
34 | } |
35 | n = x; |
36 | } |
37 | |
38 | void solve() { |
39 | h = t = 1; |
40 | Qd[t] = 1, Ql[t] = 0, Qf[t] = 1, t++; |
41 | while (h < t) { |
42 | int d = Qd[h], l = Ql[h], f = Qf[h]; |
43 | h++; |
44 | if (!mp.count(f)) { |
45 | mp[f] = d; |
46 | } |
47 | if (d >= n || d >= 35) { |
48 | continue; |
49 | } |
50 | Qd[t] = d + 1, Ql[t] = l + 1, Qf[t] = f, t++; |
51 | vis[make_pair(l + 1, f)] = true; |
52 | if (l > 1 && 1ll * f * l < inf && !vis.count(make_pair(l, f * l))) { |
53 | Qd[t] = d + 1, Ql[t] = l, Qf[t] = f * l, t++; |
54 | vis[make_pair(l, f * l)] = true; |
55 | } |
56 | } |
57 | } |
58 | |
59 | int main() { |
60 | scanf("%d %d %d", &n, &q, &m); |
61 | for (int i = 1; i <= n; i++) { |
62 | scanf("%d", &a[i]); |
63 | } |
64 | for (int i = 1; i <= n; i++) { |
65 | scanf("%d", &w[i]); |
66 | } |
67 | for (int i = 1; i <= q; i++) { |
68 | scanf("%d", &c[i]); |
69 | M = max(M, c[i]); |
70 | } |
71 | prework(); |
72 | solve(); |
73 | for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) { |
74 | F[++cnt] = it -> first, D[cnt] = it -> second; |
75 | } |
76 | for (int c, _ = 1; _ <= q; _++) { |
77 | c = c[_]; |
78 | bool flag = c <= n; |
79 | for (int i = 1; i <= cnt; i++) { |
80 | if (F[i] <= c && D[i] + c - F[i] <= n) { |
81 | flag = true; |
82 | break; |
83 | } |
84 | } |
85 | int pos = 1; |
86 | for (int i = cnt; i; i--) { |
87 | while (pos <= cnt && F[i] + F[pos] <= c) { |
88 | if (D[i] + D[pos] + c - F[i] - F[pos] <= n) { |
89 | flag = true; |
90 | break; |
91 | } |
92 | pos++; |
93 | } |
94 | if (flag) { |
95 | break; |
96 | } |
97 | } |
98 | printf("%d\n", flag); |
99 | } |
100 | return 0; |
101 | } |