P8806 [蓝桥杯 2022 国 B] 搬砖

题目描述

这天，小明在搬砖。

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

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

输入格式

输入共行, 第一行为一个正整数 , 表示砖块的数量。

后面行, 每行两个正整数分别表示每块砖的重量和价值。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

说明/提示

【样例说明】

选择第、、块砖，从上到下按照、、的顺序堆成一座塔，总价值为。

【评测用例规模与约定】

对于的数据，保证 ;

对于的数据，保证。

蓝桥杯 2022 国赛 B 组 J 题。

题解

AC Code

#include<bits/stdc++.h>
using namespace std;

int n, m, ans, dp[20025];  // dp数组大小设为20025，因为最大总重量不超过20000
struct node {
    int w, v;
} a[1005];

// 按照 w+v 从小到大排序，对应从上到下的堆叠顺序
bool cmp(node a, node b) {
    return a.w + a.v <= b.w + b.v;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i].w >> a[i].v;

    sort(a + 1, a + n + 1, cmp);  // 关键：按 w+v 排序

    for(int i = 1; i <= n; ++i) 
        // j从 w+v 到 w 枚举，保证上方砖块重量不超过当前砖的价值
        // 同时从大到小枚举保证每块砖只选一次
        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);
            ans = max(ans, dp[j]);  // 实时更新答案
        }

    cout << ans << "\n";
    return 0;
}

P8806 [蓝桥杯 2022 国 B] 搬砖题解

题目理解

我们有块砖，第块砖重量为，价值为。我们需要选择一些砖从下往上堆成塔，要求对于塔中任意一块砖，它上面所有砖的重量和不超过它自身的价值。求能堆成的塔的最大总价值。

关键思路

这道题的核心在于确定砖块的堆叠顺序。考虑两块砖 A 和 B，假设 A 在 B 的上面：

对 A 的限制：上面总重量
对 B 的限制：上面总重量

如果交换位置（B 在 A 上面）：

对 B 的限制：
对 A 的限制：

可以发现，当时，A 在上、B 在下的限制更宽松。因此，最优的堆叠顺序应该是按照从小到大从上往下排列。

动态规划

确定顺序后，问题转化为：按照排序后的顺序依次考虑每块砖，决定是否将其放在当前塔的最底部。

定义状态：dp[j] 表示当前塔的总重量为时能获得的最大价值。

对于第块砖，如果将其放在最底部，它需要承受上面所有砖的重量，因此必须满足，即。

状态转移方程：

代码解析要点

排序规则：按照从小到大排序，对应从上到下的堆叠顺序。
内层循环范围：从枚举到。上界保证了放置第块砖时，它上面的总重量，满足题目要求。
逆序遍历：从大到小枚举，保证每块砖只被使用一次（0/1背包特性）。
答案更新：每次状态转移后都实时更新答案，因为最优解不一定出现在最后一块砖。

复杂度分析

时间复杂度：，最坏情况约，可以接受。
空间复杂度：。

总结

本题的关键在于发现砖块的排序规律。通过排序将问题转化为带限制的 0/1 背包问题，限制条件恰好体现在 dp 枚举的上界中。代码实现简洁，思路巧妙，体现了动态规划中“确定顺序”的重要性。

P8806 搬砖题解