AtCoder AT_abc410_e [ABC410E] Battles in a Row 题解

题目大意

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

思路

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

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

我们考虑如何转移：

• 不使用魔力（即这一维的值为 $0$）： min ⁡ { f i − 1 , j + a i , 0 , f i − 1 , j + a i , 1 } \min\lbrace f_{i-1,j+a_i,0},f_{i-1,j+a_i,1}\rbrace min{fi−1,j+ai​,0​,fi−1,j+ai​,1​}，因为上一步体力至少剩余 $j+a_i$。
• 使用魔力（即这一维的值为 $1$）： min ⁡ { f i − 1 , j , 0 , f i − 1 , j , 1 } + b i \min\lbrace f_{i-1,j,0},f_{i-1,j,1}\rbrace+b_i min{fi−1,j,0​,fi−1,j,1​}+bi​，因为上一步体力剩余 $j$ 即可，需要额外消耗 $b_i$ 魔力。

那么如何求答案呢？显然，我们是要寻找满足最小魔力值不超过魔力上限的最大的 $i$，即满足 min ⁡ j = 0 H { f i , j , 0 , f i , j , 1 } ≤ M \min_{j=0}^H\lbrace f_{i,j,0},f_{i,j,1}\rbrace\le M minj=0H​{fi,j,0​,fi,j,1​}≤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;
}