第十三届蓝桥杯国赛 C++ B 组 J 题——搬砖（AC）

1.搬砖

1.题目描述

这天，小明在搬砖。

他一共有 $n$ 块砖, 他发现第 $i$ 砖的重量为 $w_i$, 价值为 $v_i$ 。他突然想从这些 砖中选一些出来从下到上堆成一座塔, 并且对于塔中的每一块砖来说, 它上面 所有砖的重量和不能超过它自身的价值。

他想知道这样堆成的塔的总价值（即塔中所有砖块的价值和）最大是多少。

2.输入格式

输入共 $n+1$ 行, 第一行为一个正整数 $n$, 表示砖块的数量。后面 $n$ 行, 每行两个正整数 $w_i,v_i$
分别表示每块砖的重量和价值。

3.输出格式

一行, 一个整数表示答案。

4.样例输入

5
4 4
1 1
5 2
5 5
4 3

5.样例输出

10

6.数据范围

$n\le 1000;w_i\le 20;v_i\le 20000。$

7.原题链接

搬砖

2.解题思路

诸如此题的模型，思路都是按照一种方式排序，使得最优解答案的选择情况，是排序后的一个子序列，然后直接进行背包 $dp$ 即可。

那么该如何去寻找排序的条件呢？一般的思路在于，对于砖块 $x$ 和 $y$，如果排序后的结果 $y$ 在 $x$的后面，那么对于任意 $y$ 在 $x$ 之上的摆放情况，都一定可以将两者调换。

如图，红色砖块为 $y$ 上所有砖块的重量，我们设为 $w_1$，绿色为 $x$ 与 $y$ 之间的砖块重量，我们设为 $w_2$。
根据题意可知：$v_y\ge w_1，v_x\ge w_1+w_y+w_2$，1
假设排序后 $y$ 在 $x$ 的后面，那么也一定满足：$v_x\ge w_1，v_y\ge w_1+w_x+w_2$2

因为$v_x\ge w_1+w_y+w_2$1且$w_y+w_2$一定大于 $0$，显然$v_x\ge w_1$是一定符合要求的。

然后考虑第二个式子，因为 $v_x\ge w_1+w_y+w_2$1，经过变形可得 $v_x-w_y\ge w_1+w_2$3
将式子3带入式子2可得:
$$v_y\ge w_x+v_x-w_y$$
将式子整理可得:
$$v_y+w_y\ge w_x+v_x$$
由此，我们找到了排序条件，也就是说，当满足 $v_y+w_y\ge w_x+v_x$ 时，任意 $y$ 在 $x$ 之上的摆放情况，都一定可以将两者调换

接下来就是进行背包 $dp$即可，
定义 $f[i][j]$为只考虑前 $i$ 个物品，且选择的重量为 $j$ 的最大价值。考虑如何进行转移，对于背包问题，无非是选与不选的两种抉择：

$$f[i][j]=\{\begin{array}{ll}f[i-1][j]& 不可选\\ max(f[i-1][j],f[i-1][j-w]+v)& \text{if j≥w且v≥j-w}可选\end{array}$$

题目体积最大只有2e4，答案即为从$f[n][0]$到 $f[n][20000]$取个最大值。由于是01背包问题，可以使用滚动数组进行优化。

时间复杂度:$O(nlogn+nV)$

3.Ac_code

未优化版本：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 1010;int n;
//只考虑前 i 个砖块，且重量为 j 的最大价值
int f[N][N * 20];
PII a[N];
bool cmp(PII b, PII c) {return b.first + b.second < c.first + c.second;
}
void solve()
{cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i].first >> a[i].second;}sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; ++i) {int w = a[i].first, v = a[i].second;for (int j = 0; j <= 20000; ++j) {f[i][j] = f[i - 1][j];//可选情况if (w <= j && v >= j - w) f[i][j] = max(f[i][j], f[i - 1][j - w] + v);}}int ans=0;for(int i=0;i<=20000;++i) ans=max(ans,f[n][i]);cout << ans << '\n';
}
int main()
{ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;
}

滚动数组优化：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, int> PII;
#define pb(s) push_back(s);
#define SZ(s) ((int)s.size());
#define ms(s,x) memset(s, x, sizeof(s))
#define all(s) s.begin(),s.end()
const int inf = 0x3f3f3f3f;
const int mod = 1000000007;
const int N = 1010;int n;
//只考虑前 i 个砖块，且重量为 j 的最大价值
int f[N * 20];
PII a[N];
bool cmp(PII b, PII c) {return b.first + b.second < c.first + c.second;
}
void solve()
{cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i].first >> a[i].second;}sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; ++i) {int w = a[i].first, v = a[i].second;for (int j = 20000; j >= w; --j) {//可选情况if ( v >= j - w) f[j] = max(f[j], f[j - w] + v);}}int ans = 0;for (int i = 0; i <= 20000; ++i) ans = max(ans, f[i]);cout << ans << '\n';
}
int main()
{ios_base :: sync_with_stdio(false);cin.tie(0); cout.tie(0);int t = 1;while (t--){solve();}return 0;
}