题解：B4159 [BCSP-X 2024 12 月小学高年级组] 打怪升级

· · 题解

题目链接

题目大意

我们要操控角色来玩一个游戏。这个游戏共有 n 个关卡，角色有两个属性：血量和等级。初始血量为 m。初始等级为 1，对于某一关卡，若血量 \le 0，则无法通过此关。
通关流程：先打 boss，受到一定的伤害；再使用经验书，可以选择回血或调等级。
输出：对于某一关卡，输出“通过该关后能够达到的最大等级”；若无法通过，则输出 0。

题目思路

动态规划 + 贪心

  1. 使用数组来存储每关结束后，不同等级对应的最大剩余血量。用 dp_j 表示通过前 i-1 关后，角色等级为 j 时的最大剩余血量；用 cur\_dp_j 表示通过第 i 关后，角色等级为 j 时的最大剩余血量（临时存储，便于处理）。
  2. 遍历每一关，依次进行处理。对于某一关卡，先遍历通过上一关后所有可达的等级，再计算此等级下打 boss，之后剩余的血量（若血量 \le 0，则无法通过，跳过即可），然后处理经验书的两种使用方式。具体方法代码里讲的很清楚。

    AC Code

    不要抄袭
    
#include<bits/stdc++.h>
using namespace std;

int n,m; int a[5201314]; //第i关经验书的加血量 int b[2025][2025];//第i关Boss对等级j的主角造成的伤害

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

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

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

vector<int> dp(n+2,-1);//前i-1关结束后，等级为j时的最大剩余血量（-1表示该等级不可达）
dp[1]=m;//初始化：等级1，血量m

for(int i=1;i<=n;i++)
{
    vector<int> cur_dp(n+2,-1);//存储第i关结束后的状态（临时数组）
    //遍历上一关（i-1关）所有可达的等级j（j≤i，因为第i-1关最大等级是i）
    for(int j=1;j<=i;j++)
    {
        if(dp[j] == -1)
            continue;//上一关等级j不可达，跳过

        int x=b[i][j];//第i关Boss对等级j的伤害
        int temp=dp[j]-x;//打Boss后的剩余血量（未用经验书）

        if(temp <= 0)
            continue;//血量≤0，无法通过本关，跳过

        //选择1：回血
        //回血后血量 = temp + a[i]，等级仍为j；若该等级当前血量更大，更新cur_dp[j]
        if(temp+a[i] > cur_dp[j])
            cur_dp[j]=temp+a[i];

        //选择2：调等级
        //等级可改为 [1, j+1]，遍历所有可能的新等级new_j
        for(int new_j=1;new_j<=j+1;new_j++)
        {
            // 不回血，血量仍为temp；若新等级new_j的当前血量更大，更新cur_dp[new_j]
            if(temp > cur_dp[new_j])
                cur_dp[new_j]=temp;
        }
    }

    //计算第i关的答案：找cur_dp中可达的最大等级
    int ans=0;//初始为0（不可达）
    //从最大可能等级往下找，第一个可达等级就是最大等级
    for(int j=n+1;j>=1;j--)
    {
        if(cur_dp[j] != -1)
        {
            ans = j;
            break;
        }
    }
    cout << ans << "\n";//输出

    dp=move(cur_dp);//将当前关状态覆盖至dp
}

return 0;

}