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

· · 题解

由于数据太水，O(n^3) 的做法也可以过，这里给出一个 O(n^2) 的做法。

我们可以令 dp_{i, j} 表示第 i 关结束后等级为 j 的最大血量。分为加血量和加等级两种情况，容易推出转移方程：

dp_{i,j}=\max(dp_{i,j},dp_{i-1,j}-b_{i,j}+a_i) \\ dp_{i,j}=\max(dp_{i,j},dp_{i-1,k}-b_{i,k})(k\in [j-1,i]) \end{cases}

此 O(n^3) 的做法与前两篇题解不同之处在于这是以 i 的视角来推倒的，这也便于后面的优化。

复杂度瓶颈在于第二个式子，考虑优化。由与每次 k 取值的右端点不变，考虑后缀 max。具体实现就是维护一个变量 maxn。倒序枚举 j，每次左端点左移一格，就将左端点对应的值更新进 maxn。也可以写一个数组，但这种方法被莫名其妙地卡掉了，所以就不详细说了。（我考试的时候就是这么写的，结果被捆绑测试卡到了 39 分）

如果加强了数据，建议升绿，因为本来朴素就很容易想歪，加优化还是挺难的。

贴上代码：

#include <iostream>
using namespace std;

const int N = 1505;
int a[N], b[N][N], dp[N][N], maxn[N];

int main()
{
    int n, m;
    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];
    dp[0][1] = m;
    for (int i = 1; i <= n; i++)
    {
        int maxn = 0;
        for (int j = i + 1; j >= 1; j--)
        {
            if (dp[i - 1][j] - b[i][j] > 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j] - b[i][j] + a[i]);

            maxn = max(maxn, dp[i - 1][j - 1] - b[i][j - 1]);
            if (maxn <= 0) continue;
            dp[i][j] = max(dp[i][j], maxn);
        }
        int ans = 0;
        for (int j = i + 1; j >= 1; j--)
        {
            if (dp[i][j] > 0)
            {
                ans = j;
                break;
            }
        }
        cout << ans << endl;
    }
    return 0;
}