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

傷城~ 2023-09-29 20:47 20阅读 0赞

#### 目录 ####

*  1.搬砖
 *   *  1.题目描述
     *  2.输入格式
     *  3.输出格式
     *  4.样例输入
     *  5.样例输出
     *  6.数据范围
 *  7.原题链接
 *  2.解题思路
 *  3.Ac\_code

## 1.搬砖 ##

### 1.题目描述 ###

这天，小明在搬砖。

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

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

### 2.输入格式 ###

输入共  n + 1 n+1 n\+1 行, 第一行为一个正整数  n n n, 表示砖块的数量。后面  n n n 行, 每行两个正整数  w i , v i w\_i ,v\_i wi,vi  
分别表示每块砖的重量和价值。

### 3.输出格式 ###

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

### 4.样例输入 ###

5  
4 4  
1 1  
5 2  
5 5  
4 3

### 5.样例输出 ###

### 6.数据范围 ###

n ≤ 1000 ; w i ≤ 20 ; v i ≤ 20000 。 n≤1000;w\_i ≤20;v\_i ≤20000 。 n≤1000;wi≤20;vi≤20000。

## 7.原题链接 ##

[搬砖][Link 1]

## 2.解题思路 ##

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

那么该如何去寻找排序的条件呢？一般的思路在于，对于砖块  x x x 和  y y y，如果排序后的结果  y y y 在  x x x的后面，那么对于任意  y y y 在  x x x 之上的摆放情况，都一定可以将两者调换。  
![在这里插入图片描述][7554d0730bae49e0a362ab5ce67397db.png]  
如图，红色砖块为  y y y 上所有砖块的重量，我们设为  w 1 w\_1 w1，绿色为  x x x 与  y y y 之间的砖块重量，我们设为  w 2 w\_2 w2。  
根据题意可知： v y ≥ w 1 ， v x ≥ w 1 + w y + w 2 v\_y≥ w\_1，v\_x≥w\_1+w\_y+w\_2 vy≥w1，vx≥w1\+wy\+w2，`1`  
假设排序后  y y y 在  x x x 的后面，那么也一定满足： v x ≥ w 1 ， v y ≥ w 1 + w x + w 2 v\_x≥ w\_1，v\_y≥w\_1+w\_x+w\_2 vx≥w1，vy≥w1\+wx\+w2`2`

因为 v x ≥ w 1 + w y + w 2 v\_x≥w\_1+w\_y+w\_2 vx≥w1\+wy\+w2`1`且 w y + w 2 w\_y+w\_2 wy\+w2一定大于  0 0 0，显然 v x ≥ w 1 v\_x≥ w\_1 vx≥w1是一定符合要求的。

然后考虑第二个式子，因为  v x ≥ w 1 + w y + w 2 v\_x≥w\_1+w\_y+w\_2 vx≥w1\+wy\+w2`1`，经过变形可得  v x − w y ≥ w 1 + w 2 v\_x-w\_y≥w\_1+w\_2 vx−wy≥w1\+w2`3`  
将式子`3`带入式子`2`可得:  
 v y ≥ w x + v x − w y v\_y≥w\_x+v\_x-w\_y vy≥wx\+vx−wy  
将式子整理可得:  
 v y + w y ≥ w x + v x v\_y+w\_y≥w\_x+v\_x vy\+wy≥wx\+vx  
由此，我们找到了排序条件，也就是说，**当满足  v y + w y ≥ w x + v x v\_y+w\_y≥w\_x+v\_x vy\+wy≥wx\+vx 时，任意  y y y 在  x x x 之上的摆放情况，都一定可以将两者调换**

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

f \[ i \] \[ j \] = \{ f \[ i − 1 \] \[ j \] 不可选 m a x ( f \[ i − 1 \] \[ j \] , f \[ i − 1 \] \[ j − w \] + v ) if j≥w且v≥j-w可选 f\[i\]\[j\] = \\begin\{cases\} f\[i-1\]\[j\] &不可选\\\\ max(f\[i-1\]\[j\],f\[i-1\]\[j-w\]+v) &\\text\{if j≥w且v≥j-w\} 可选\\\\ \\end\{cases\} f\[i\]\[j\]=\{ f\[i−1\]\[j\]max(f\[i−1\]\[j\],f\[i−1\]\[j−w\]\+v)不可选if j≥w且v≥j-w可选

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

时间复杂度: O ( n l o g n + n V ) O(nlogn+nV) 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;
    }

[Link 1]: https://www.lanqiao.cn/problems/2201/learning/?page=1&first_category_id=1&sort=students_count&name=%E6%90%AC%E7%A0%96
[7554d0730bae49e0a362ab5ce67397db.png]: https://img-blog.csdnimg.cn/7554d0730bae49e0a362ab5ce67397db.png