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

目录

• 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.样例输出

    10

    6.数据范围

    n ≤ 1000 ; w i ≤ 20 ; v i ≤ 20000 。 n≤1000;w_i ≤20;v_i ≤20000 。 n≤1000;wi​≤20;vi​≤20000。

    7.原题链接

    搬砖

    2.解题思路

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

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

    如图，红色砖块为 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

    未优化版本：

    #includeusing namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef pair 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;
    }
    

    滚动数组优化：

    #includeusing namespace std;
    typedef long long LL;
    typedef unsigned long long uLL;
    typedef pair 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;
    }