【题解】HNOI2017大佬

　　哎……做了几个小时最后还是没能想到怼大佬的合法性到底怎么搞。写暴力爆搜感觉复杂度爆炸就没敢写 bfs / dfs 一类，后来发现在种种的约束条件下（远小于所给的 \(n, m\)）复杂度完全是可以承受的。不过就算想到了这一步谅我也想不出用单调栈来搞两次的组合吧。

　　这题最开始就应该发现：扣血和回血完全是可以分开的两个操作。为什么这个点很容易发现呢：1.扣血的多少与时间是无关的。2.本题要求活着（血量 >= 0）而非最大化血量。所以第一步显然应当 dp 出在保证活着的前提下最多能够空出多少天来对付 ‘大佬’。

　　然后来考虑，假设我们最多拥有 \(D\) 天来攻击，是否存在一种攻击方案使得'大佬'的血量正好为0。预处理出 \(g[k][d]\) 代表 \(d\) 次操作，是否可能对'大佬'产生 \(k\) 点伤害。（这里用Map来存储，并注意这里的方案只考虑怼一次）。然后我们假设存在一种合法的方案怼大佬两次使得大佬血量正好为0，第一次扣血 \(f1\) 点，耗费时间为 \(d1\) 天，第二次扣血 \(f2\) 点，耗费时间为 \(d2\) 天。他们之间该满足什么样的关系式呢？（设大佬血量为 \(M\)）

\(M >= f1 + f2\)

\(M - f1 - f2 <= D - d1 - d2\)

　　其中（1）式表示不能减为负数，（2）式表示没有减完的血量可以通过还嘴来减掉。之后将（2）式移项（构造常量与非常量之间的不等式以方便检查）

\(D >= M - f1 - f2 + d1 + d2\)

　　然后我们选择枚举这两次怼大佬之间的其中一个，则不确定的项即为 \(d2 - f2\) ，因为要求右边的小，所以求这个的最小值之后判断就好了。又因为有之前（1）式的约束，我们在固定了 \(f1\) 后如果能够将 \(f\) 从小到大排序，即可方便判断何时一定不满足（单调递增）。

#include <bits/stdc++.h>

using namespace std;

#define maxn 110

#define ll long long

#define INF 990000000

int n, m, mc, a[maxn], w[maxn];

int ans, maxx, top, B[maxn];

int mark[maxn], f[maxn][maxn];

pair <int, int> S[];

map <int, int> Map[maxn];

struct node

{

    int num, v, lev;

};

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void upmax(int &x, int y) { x = x > y ? x : y; }

void DP()

{

    for(int i = ; i <= n; i ++)

        for(int j = ; j <= mc - a[i]; j ++)

            {

                upmax(f[i][min(mc, j + w[i])], f[i - ][j + a[i]]); // add blood

                upmax(f[i][j], f[i - ][j + a[i]] + ); // do nothing

                ans = max(f[i][j], ans);

            }

}

void BFS(int tot)

{

    queue <node> q; q.push((node) {, , });

    while(!q.empty())

    {

        node x = q.front(); q.pop();

        if(x.num < tot)

        {

            q.push((node) {x.num + , x.v, x.lev + });

            if(x.lev >  && x.v < maxx / x.lev && !Map[x.lev][x.v * x.lev])

            {

                node y = (node) { x.num + , x.v * x.lev, x.lev};

                Map[x.lev][x.v * x.lev] = ;

                S[++ top] = make_pair(y.v, y.num); q.push(y);

            }

        }

    }

}

int main()

{

    n = read(), m = read(), mc = read();

    for(int i = ; i <= n; i ++) a[i] = read();

    for(int i = ; i <= n; i ++) w[i] = read();

    for(int i = ; i <= m; i ++) B[i] = read(), maxx = max(maxx, B[i]);

    memset(f, , sizeof(f)); f[][mc] = ; DP();

    BFS(ans); sort(S + , S + top + );

    for(int i = ; i <= m; i ++)

    {

        int t = B[i], fans = , fmin = INF;

        if(t < ans) { printf("1\n"); continue; }

        for(int j = top, k = ; j; j --)

        {

            while(k <= top && S[k].first + S[j].first <= t)

                fmin = min(fmin, S[k].second - S[k].first), k ++;

            if(fmin + t - S[j].first + S[j].second <= ans) { fans = ; break; }

            if(S[j].first <= t && S[j].second + t - S[j].first <= ans) { fans = ; break; }

        }

        printf("%d\n", fans);

    }

    return ;

}

巴特西

【题解】HNOI2017大佬

最新文章

热门文章