自动搬运

查看原文

来自洛谷，原作者为

	tomAmy 你好呀，有缘人～

搬运于2025-08-24 21:17:28，当前版本为作者最后更新于2025-05-05 15:23:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

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

$$\begin{cases} 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;
}