题解：AT_abc410_e [ABC410E] Battles in a Row

· · 题解

原题

题意

给定一个生命值和魔法值还有 n 只怪物，第 i 只怪物要么使用 a_i 生命值要么使用 b_i 魔法值，且不能跳过，如果打不过则退出，求最多能打过的怪物数量。

思路

这题很明显是 dp，但是状态 dp_{i, j, k} 表示打了前 i 只怪物，还剩 j 点生命 k 点魔法显然爆空间了，我们发现当还剩 i 点生命时魔法越多越好，所以我们可以优化状态为 dp_{i, j} 表示打到第 i 只怪物还剩 j 点生命消耗的最少魔法值。转移方程就是：

dp_{i, j} = \min(dp_{i - 1, j} + b_i, dp_{i - 1, j - a_i})

时空复杂度

时间复杂度：O(n \times h)

空间复杂度：O(n \times h)

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 3e3 + 3;
const int INF = 1e9;

int n, h, m, a[N], b[N], dp[N][N], ans;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> h >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
  }
  for (int i = 1; i <= n; i++) {
    bool f = 0;
    for (int j = 0; j <= h; j++) {
      dp[i][j] = dp[i - 1][j] + b[i];                            // 使用魔法
      if (j >= a[i]) {
        dp[i][j] = min(dp[i][j], dp[i - 1][j - a[i]]);           // 使用生命
      }
      f |= dp[i][j] <= m;                                        // 判断这个怪物能不能打败
    }
    ans += f;
    if (!f) {
      break;
    }
  }
  cout << ans;
  return 0;
}