AT_abc410_e

· · 题解

博客

请点击这里享受更好的阅读效果！

题目大意

高桥有两种属性：体力（共 H 点）和魔力（共 M 点）。现在要按顺序处理 N 个怪兽，可以使用 a_i 点体力或者 b_i 点魔力，处理到体力魔力不足或全部完成为止。问最多处理几个怪兽。

思路

题目明确了我们要按顺序处理，这也大大节省了时间复杂度（无需枚举上一步所在位置）。我们令 f_{i,j,0/1} 表示处理第 i 个怪兽，还剩 j 点体力，是否（0 代表否，1 代表是）在这次使用魔力的情况下，最少需要消耗多少魔力。

我个人认为最好不要把第一位压掉，不然很有可能会造成第 i 步未由第 i-1 步转移而来的情况。在这种情况下，空间只能开一个 O(NH) 或者 O(NM) 的了（常数忽略不计）。所以，我们不能按照正常的思路去开三维数组直接计算答案，而是要这样间接地完成。如果你之前没有接触过这样的动态规划方式，建议完成 洛谷 P1510 精卫填海 之后再来阅读本文。

我们考虑如何转移：

那么如何求答案呢？显然，我们是要寻找满足最小魔力值不超过魔力上限的最大的 i，即满足 \min_{j=0}^H\lbrace f_{i,j,0},f_{i,j,1}\rbrace\le M 的最大的 i。

代码

// https://atcoder.jp/contests/abc410/submissions/66760787
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n, h, m;
int a[3010];
int b[3010];
int f[3010][3010][2];

int main()
{
    cin >> n >> h >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];
    memset(f, 0x3f, sizeof(f));
    for (int i = 0; i <= h; i++)
        f[0][i][0] = f[0][i][1] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j + a[i] <= h; j++)
        {
            f[i][j][0] = f[i - 1][j + a[i]][0];
            f[i][j][0] = min(f[i][j][0], f[i - 1][j + a[i]][1]);
        }
        for (int j = 0; j <= h; j++)
        {
            f[i][j][1] = f[i - 1][j][0];
            f[i][j][1] = min(f[i][j][1], f[i - 1][j][1]);
            f[i][j][1] += b[i];
        }
    }
    for (int i = n; i >= 0; i--)
    {
        int v = 1e9;
        for (int j = 0; j <= h; j++)
            v = min(v, min(f[i][j][0], f[i][j][1]));
        if (v <= m)
        {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}