P8806 [蓝桥杯 2022 国 B] 搬砖

一、问题简析

本题采用 贪心 + 01背包。

令 \(a_i=\) 第 \(i\) 块砖; \(a_i.w=\) \(a_i\) 的质量; \(a_i.v=\) \(a_i\) 的价值。本题与 01背包 模板不同的地方是，本次选择的砖块会对后续的选择产生影响。为了使承重能力强的砖块留在最后选，贪心地优先选择承重能力弱的砖块。所以，要对砖块按 \(a_i.w+a_i.v\) （即承重能力）升序排序。

证明：若 \(a_i.w+a_i.v < a_j.w+a_j.v\)，则 \(a_i\) 的承重能力弱于 \(a_j\)。
假设 \(a_i\) 和 \(a_j\) 无论上下都合法。

• 若 \(a_i\) 在 \(a_j\) 上面，则 \(a_j\) 还能承重 \(a_j.v-a_i.w\)。
• 若 \(a_i\) 在 \(a_j\) 下面，则 \(a_i\) 还能承重 \(a_i.v-a_j.w\)。
  由条件 \(a_i.w+a_i.v < a_j.w+a_j.v\)，变换得 \(a_i.v-a_j.w<a_j.v-a_i.w\)。显然 \(a_j\) 的承重能力优于 \(a_i\)，应优先选择承重能力弱的 \(a_i\)。

二、Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll quickin(void)
{
	ll ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

struct node{int w, v;};
const int MAX = 2e4 + 10;
node A[1010];
int n, dp[MAX];

bool cmp(const node &a, const node &b)
{
	return a.w + a.v < b.w + b.v; 
}

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	int sum = 0;
	n = quickin();
	for (int i = 1; i <= n; ++i)
	{
		A[i].w = quickin();
		A[i].v = quickin();
		
		sum += A[i].w;
	}
	
	sort(A + 1, A + 1 + n, cmp);
	
	for (int i = 1; i <= n; ++i)
	{
		for (int j = A[i].w + A[i].v; j >= A[i].w; --j)
		{
			dp[j] = max(dp[j], dp[j - A[i].w] + A[i].v);
		}
	}
	
	int ans = 0;
	for (int i = 0; i <= sum; ++i)
		ans = max(ans, dp[i]);
	
	cout << ans << endl;
	
	return 0;
}

完