BZOJ4828 「HNOI2017」大佬

题解
BFS, two pointers, 动态规划

Description

你现在要怼 $m$ 个大佬，第 $i$ 个大佬的自信值是 $C_i$ 。每次怼大佬之前，你的自信值是 $mc$，等级 $L=0$，嘲讽值 $F = 1$。对于每一个大佬，你都有 $n$ 天时间来怼大佬。无论哪个大佬，他们都会在第 $i$ 天使你的的自信值下降 $a_i$ 如果你的自信值为负数，那么你失败了。在第 $i$ 天，你可以干一下事情中的恰好一件：

  1. 使得大佬自信值下降 $1$
  2. 使得自己的自信值增加 $w_i$
  3. 把自己的等级 $+1$
  4. 把自己的 $F$ 乘上 $L$
  5. 怼大佬，使得大佬的自信值下降 $F$，之后$L=0$ ，$F=1$

如果中途大佬自信值为负数，你失败了。若大佬自信值恰好为 $0​$ ，则你成功了。

对于每个大佬求你能否成功。

Solution

首先，可以发现，怼大佬和活下来两件事是互相独立的。并且怼大佬只与天数相关。显然天数越多越有可能。

所以先用一遍简单 dp 得出最多能剩下多少天来怼大佬并且保证自己活下来。设最多天数是 $D$ 。

然后用一遍 BFS 的出所有二元组 $(d, f)$ 表示用了 $d(<D)$ 天并且此时 $F = f$ 。注意去重。

你能怼死大佬有三种情况：

  1. 不怼大佬。只执行 $1$ 操作。此时需要满足 $C_i \leq D$
  2. 只怼一次大佬。这时能怼死大佬需要满足存在一个二元组 $(d’,f’)$ 使得 $f’ \leq C_i$ 并且 $f’+D - d \ge C_i$ （一次不能怼死，用 $1$ 操作耗死）
  3. 怼两次。可以发现，若两次分别是 $(d_1,f_1), (d_2, f_2)$ 则类似于第二种情况，有 $f_1+f_2\leq C_i$ 并且 $f_1+f_2+(D-d_1-d_2) \ge C_i$ 。显然，对于一个 $f_i$ ，只有最小的那个 $d_i$ 才是最优的。所以我们对每个 $f$ 只保存最小的 $d$ ，并且按照 $f$ 排序。由于需要满足$f_1+f_2\leq C_i$， 就可以直接用双指针扫一遍，中途判断是否存在 $f_1+f_2+(D-d_1-d_2) \ge C_i$ 即可。

由于 $f$ 增长的很快，导致二元组不会特别多，于是可以通过此题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/**
 * Author: AcFunction
 * Date:   2019-06-21 14:35:24
 * Email:  3486942970@qq.com
**/
 
#include <bits/stdc++.h>
#define PII pair <int, int> 
#define fi first 
#define se second 
#define MP make_pair
 
using namespace std;
 
const int N = 105; 
const int NN = (int)3e6 + 10; 
const int INF = (int)1e9; 
 
int n, m, mc, mxc, cnt, tot; 
int a[N], w[N], dp[N][N], D, C[22]; 
 
pair <int, PII> Q[NN]; 
PII A[NN], B[NN]; 
map <PII, int> mp; 
map <int, int> mmp; 
 
void getday() {
  for(int i = 1; i <= n; i++) {
    for(int j = a[i]; j <= mc; j++) {
      dp[i][j - a[i]] = max(dp[i][j - a[i]], dp[i - 1][j] + 1); 
      int t = min(j - a[i] + w[i], mc); 
      dp[i][t] = max(dp[i][t], dp[i - 1][j]); 
    }
  }
  for(int i = 1; i <= n; i++) 
    for(int j = 0; j <= mc; j++)
      D = max(D, dp[i][j]); 
}
 
void getst() {
  int h = 1, t = 0;
  // fi : day
  // se.fi : level
  // se.se : att
  Q[++t] = MP(1, MP(0, 1)); 
  mp[MP(1, 1)] = 1; 
  while(h <= t) {
    pair <int, PII> tmp = Q[h++]; 
    if(tmp.fi >= D) continue ; 
    int d = tmp.fi, l = tmp.se.fi, f = tmp.se.se;
    Q[++t] = MP(d + 1, MP(l + 1, f)); 
    mp[MP(d + 1, f)] = 1; 
    if(l > 1 && 1ll * l * f <= mxc && !mp[MP(d + 1, l * f)]) {
      int nf = l * f; 
      Q[++t] = MP(d + 1, MP(l, nf)); 
      mp[MP(d + 1, nf)] = 1; A[++cnt] = MP(d + 1, nf); 
    }
  }
}
 
bool cmp(PII a, PII b) {
  return a.se == b.se ? a.fi < b.fi : a.se < b.se; 
}
 
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]); 
    mxc = max(mxc, C[i]); 
  }
  getday(); 
  getst(); 
  sort(A + 1, A + cnt + 1, cmp); 
  for(int i = 1; i <= cnt; i++) {
    if(!mmp[A[i].se]) {
      mmp[A[i].se] = 1; 
      B[++tot] = A[i]; 
    }
  }
  for(int _ = 1; _ <= m; _++) {
    if(C[_] <= D) {
      puts("1"); 
      continue ; 
    }
    int ok = 0, pos = 1; 
    for(int i = tot; i >= 1; i--) {
      int d = B[i].fi, f = B[i].se;
      if(f <= C[_] && D - d + f >= C[_]) {
        ok = 1; break ; 
      }
      int mx = -INF; 
      while(pos <= tot && f + B[pos].se <= C[_]) {
        mx = max(mx, B[pos].se - B[pos].fi); pos++; 
      } 
      if(f - d + mx >= C[_] - D) {
        ok = 1; break ; 
      } 
    }
    printf("%d\n", ok); 
  }
  return 0; 
}