[HNOI 2017]大佬

Description

题库链接

题意简述来自Gypsophila。

你现在要怼 \(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\)（该操作最多使用 2 次）
6. 如果中途大佬自信值为负数，你失败了。若大佬自信值恰好为 \(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\) 天内砍大佬。

1. 不用“怼大佬”。显然，若是 \(C_i\leq maxd\)，可以直接把大佬砍死；
2. 用一次“怼大佬”，我们记怼大佬用的时间（准备时间（累加 \(L\) 和累乘 \(F\) 的时间）+怼大佬的那天）为 \(d\)，造成的伤害为 \(f\)。那么由于不能把大佬砍成负，要满足 \(f\leq C_i\)，又要把大佬砍到 0，因此 \(f+maxd-d\geq C_i\);
3. 用两次“怼大佬”，我们记怼大佬用的时间分别为为 \(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 
#define pii pair
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 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;
}