自动搬运

查看原文

来自洛谷，原作者为

	ylch 博观而约取，厚积而薄发 加油！（查看.com域名帖子中的内容，把后缀改成.me即可）

搬运于2025-08-24 23:03:59，当前版本为作者最后更新于2024-11-09 19:43:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Description

抽象题意：有 $n$ 种、$k$ 个物品，和一个体积为 $m$ 的背包，每个物品的收益为 $a_i$，体积为 $b_i$。

你只能依次选择这 $k$ 个物品，且无法跳过不选。

为了获得更多的收益，有一种超能力，可以从 $n$ 种物品中选择若干种物品，并在这些种类的物品第一次出现时放弃选择该种物品。

求最后能获得的最大收益。

Analysis

这道题的正解是 01 背包。（我个人认为出题人的解法复杂度并不稳定，可能只是因为随机数据卡过去了）

具体地，首先用前缀和的思想统计所有的经验和损失，然后顺序遍历 $k$ 次攻击，假设当前是第 $i$ 次攻击，同时当前血量 $m<0$，那么，我们就要想办法从前面防御一些攻击，使得血量刚好可以回正（即减少 $1-m$ 的伤害），同时又不损失过多的经验。

那么，我们可以在每种物品第一次出现时，做一次 01 背包，得到要回一定血量所需的最小代价。

然后，对于血量 $m<0$ 的情况，通过在总经验上减去 $dp[1-m]$ 的经验，来维持血量，同时统计经验最大值

注意两个细节：

1. 我们减去的 $dp[1-m]$ 的经验要取后缀最小值，因为会出现回血多、经验值损失反而少的情况（题目并不保证失去血量越大，经验值越多）。

2. 我们“减去经验”“回血”等都是为了统计答案所使用，不能改变正常的血量、前缀和，因为这只是我们做出的“假设”，不对正常状况做出影响。

   也可以这么理解：这里的经验损失、回血一定会在之后的循环中被其他 dp 状态所包含（因为越往后累计伤害越大、被迫损失经验越多）。

这样时间复杂度为 $O(k + n^2 \times C)$，因为每种攻击只在第一次出现时跑 dp，所以背包 dp 的循环只会执行 $n$ 次。 同时，题目的血量最大值 $C \le 10^5+5$，数组的空间不会超限。

Summary

这道题和普通 01 背包的区别是：这道题是随着 $k$ 次伤害的遍历、是否有某种攻击的首次出现来进行 dp， 而不是传统的先对全部情况 dp 预处理，再在处理询问时直接输出。

这道题可以更好地加深我们对传统背包 dp 的理解。

Code

附详细注释。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 30, maxk = 2e7 + 5;
const int M = 1e9, C = 1e5 + 5;

int n, m, k, s;
int a[maxn], b[maxn], c[maxk];
ll dp[C * maxn], suf[C * maxn]; // dp[j]表示（前i种攻击）剩余血量为j时，得到的最小经验值；suf是后缀最小值
bool vis[maxn]; // vis[i]表示第i种攻击是否出现过

void solve()
{
	cin>>n>>m>>k>>s;
	mt19937 rand(s);
	for(int i=1;i<=n;i++)  a[i]=rand()%M+1,b[i]=rand()%C+1;
	for(int i=1;i<=k;i++)  c[i]=rand()%n+1;
	
	// 初始化为较大值（加法不爆）
	memset(dp, 0x3f, sizeof dp);
	memset(suf, 0x3f, sizeof suf);
	dp[0] = 0;
	
	ll sum = 0, maxn = 0; // s统计经验前缀和、maxn统计能获得的最大经验
	for(int i = 1; i <= k; i ++){
		if(!vis[c[i]]){ // 如果这是第c[i]种攻击第一次出现
			vis[c[i]] = 1;
			// 背包dp
			for(int j = C * n; j >= b[c[i]]; j --){ // 注意滚动数组要倒着遍历，避免提前计算
				dp[j] = min(dp[j], dp[j - b[c[i]]] + a[c[i]]);
			}
			// 统计后缀最小值
			for(int j = C * n; j >= 0; j --){
				suf[j] = min(suf[j + 1], dp[j]);
			}
		}
		
		sum += a[c[i]];
		if(m <= 0){
			// 防止越界 和 不存在的状态被计入答案
			if(1 - m <= C * n && suf[1 - m] != LLONG_MAX){
				maxn = max(maxn, sum - suf[1 - m]);
				// 这里不用把sum减去经验值，因为回血只是为统计做出的假设，不影响正常进程
			}
			else break; // 否则说明救不回来了，退出循环即可
		}
		else{ // 注意这个else非常关键，因为如果进了上一个if，当前统计上的s应该是减去一部分经验值的，而不是原值
			maxn = max(maxn, sum);
		}
		m -= b[c[i]]; // 和sum同理，这里不用把m回正
	}
	
	cout << maxn << '\n';
}

signed main()
{
	ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	solve();
	return 0;
}

End

管理员大大辛苦啦~

谢谢大家！