专栏文章

AT_abc410_e [ABC410E] Battles in a Row 题解

wwangzhechun
AT_abc410_e题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip33ljl
此快照首次捕获于
2025/12/03 05:22
3 个月前
此快照最后确认于
2025/12/03 05:22
3 个月前
查看原文

(づ｡◕‿‿◕｡)づAT_abc410_e [ABC410E] Battles in a Row 题解

题目传送门
博客查看更佳

题意

高桥要依次打 NN 个怪兽，他在最初时有 HH 点体力值和 MM 点魔力值。
对于每个怪兽，他可以消耗 AiA_i 点体力值击败，也可以消耗 BiB_i 点魔力值击败。任意时刻，他的剩余体力值和剩余魔力值都不能为负。
问他能打最多多少个怪兽。

题解

显然我们可以用 DP 解决这道题。定义 dp[i][h]=mdp[i][h]=m 表示打败第 ii 个怪兽，剩余 hh 点体力时最大魔力值为 mm。初始化 dp[0][H]=Wdp[0][H]=W，其余都为 −1-1。
考虑转移，每次有两种情况。
  • 使用体力值。则 dp[i][j−a[i]]=max⁡(dp[i][j−a[i]],dp[i−1][j])dp[i][j-a[i]]=\max(dp[i][j-a[i]],dp[i-1][j])。
  • 使用魔力值。则 dp[i][j]=max⁡(dp[i][j],dp[i−1][j]−b[i])dp[i][j]=\max(dp[i][j],dp[i-1][j]-b[i])。
每次转移后，若能打过则更新答案，最后输出即可。
代码：
CPP
#include <bits/stdc++.h>
using namespace std;
int n, h, m, a[3001], b[3001], dp[3001][3001], ans;
int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n >> h >> m;

    for (int i = 1; i <= n; i++)
        cin >> a[i] >> b[i];

    memset(dp, -1, sizeof(dp));
    dp[0][h] = m;

    for (int i = 1; i <= n; i++) {
        for (int j = a[i]; j <= h; j++) {
            dp[i][j - a[i]] = max(dp[i][j - a[i]], dp[i - 1][j]);

            if (dp[i][j] > -1)
                ans = i;
        }

        for (int j = 0; j <= h; j++) {
            dp[i][j] = max(dp[i][j], dp[i - 1][j] - b[i]);

            if (dp[i][j] > -1)
                ans = i;
        }
    }

    cout << ans;
    return 0;
}   //Code by wangzhechun
赛时提交记录
然后我们就可以完美的 AC 这道题啦~(≧▽≦)/~。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...