\(\text{Solution}\)

我们发现5个行为中2操作与其它操作无关，所以我们采用贪心，尽量让多的时间去攻击大佬。

设 \(f[i][j]\) 表示前 \(i\) 天剩 \(j\) 血量所能攻击的最多次数，是个很简单的 \(dp\) ，决策就是刷不刷水题， ​\(D​\) 就是最多的时间。

void DP() {  memset(f, -1, sizeof f);  f[0][MC] = 0;   for (int i = 0; i < n; ++ i)    for (int j = 0; j <= MC; ++ j) {      if (f[i][j] == -1) continue;      chkmax(D, f[i][j]);      int t = j - a[i + 1];       if (t < 0) continue;      chkmax(f[i + 1][t], f[i][j] + 1);      t = min(t + w[i + 1], MC);      chkmax(f[i + 1][t], f[i][j]);    }}

那么现在就是给你很多组询问，询问是否能在 \(D\) 天内击败大佬。

考虑一个二元组 \((x, y)\) 表示达到讽刺值为 \(x\) ，能力值为 \(y\) 的最少天数。

然后这些二元组我们可以从 \((1,0)\) \(bfs\)暴力求。

void Get() {  queue
    
      Q;  Q.push(pii(1, 0));  M[pii(1, 0)] = 0;  while (Q.size()) {    pii x = Q.front(); Q.pop();    int now = M[x];    if (vis[x.first])      chkmin(V[x.first], now + 1);    else {//V[x]: 至少到V[x]天讽刺值为x,并且明天可以继续累积      vis[x.first] = 1;      b[++tot] = x.first;      V[x.first] = now + 1;    }    if (now >= D - 1) continue;//明天不能继续累积，只能攻击    if (!M.count(pii(x.first, x.second + 1))) {//升级      M[pii(x.first, x.second + 1)] = now + 1;      Q.push(pii(x.first, x.second + 1));    }    if (x.second > 1 && 1ll * x.first * x.second < maxM &&        !M.count(pii(x.first * x.second, x.second))) {//累积讽刺值        M[pii(x.first * x.second, x.second)] = now + 1;        Q.push(pii(x.first * x.second, x.second));    }  }}
    

求出二元组后，对所有二元组按讽刺值排序(第一维)，记 \(g[i]\) 为第 \(i\) 个二元组 \(x_i-y_i\) 的值。

考虑不怼大佬，回嘴击败大佬：

if (C < D) return true;

考虑怼一次大佬，需满足有 \(x_i\le C​\) \(\text{and}​\) \(C\le x_i +(d -y_i)=g[i]+d​\)

for (int i = 1; i <= tot; ++ i)    if (C >= x[i] && g[i] >= C - D)         return 1;//怼一次

考虑怼两次大佬，需满足有 \(x_i+x_j\le C\ \text{and}\ C\le x_i+x_j+(d-y_i-y_j)\)

两个指针扫描，由于排好序先保证 \(x_i+x_j\le C\) 然后维护前缀 \(g[i]\) 最大值 \(Mx[i]\)

for (int i = 1; i <= tot; i++) {    if (x[i] > c)         return 0;//如果当前大于c，那么之后必然大于c，不满足条件1,是一个小剪枝    while (tail && x[i] + x[tail] > C)         --tail;//由于x单调，可能的答案在i到tail之间    if (tail && g[i] + Mx[tail] >= C - D)         return 1;}

这题难就难在将原问题抽离成两个单独的问题，将复杂的问题抽离成一些容易的，比较好处理的问题，会对结题有很大帮助，然后就是要多积累，熟悉经典问题的解法，如本题的讨论怼几次的问题上为了满足条件，运用了双指针扫描 \((two\_pointer)\) 的方法。

\(\text{Source}\)

#include 
    
     #include