1 条题解

  • 0
    @ 2026-11-12 21:58:21

    [X] Tower(dp_x)题解

    题意简述

    NN 块积木,第 ii 块重量 wiw_i、坚固度 sis_i、价值 viv_i。挑若干块堆成塔,要求塔中每块积木上方的总重不超过其 sis_i。求价值之和最大。

    思路

    第一步:确定最优堆叠顺序

    结论:把积木按 wi+siw_i + s_i 升序从下往上堆(或等价地:排序后按顺序做 0/1 背包)。

    证明(交换论证):设两块积木 A,BA, B 相邻,AA 在上、BB 在下,需要

    ∑上方+wA≤sB.\sum_{\text{上方}} + w_A \le s_B .

    若 wA+sA≤wB+sBw_A + s_A \le w_B + s_B,则把 BB 放到 AA 上面也是合法的(可验证约束不会变紧)。因此总存在一个"按 w+sw+s 升序自下而上"的最优方案。

    第二步:DP

    按 wi+siw_i+s_i 排好序后,从前到后(自下而上)决定放不放:

    设 fjf_j = 已选积木的总重为 jj 时的最大价值。

    放第 ii 块时,它将被放在已有塔的下面,所以要求"上方总重" j≤sij \le s_i:

    $$f_{j + w_i} = \max\left( f_{j+w_i},\; f_j + v_i \right) \quad (j \le s_i).$$

    注意 jj 从大到小枚举(0/1 背包)。

    第三步:重量的上界

    塔的总重不会超过"最底下一块"的 w+sw + s,因为最底下的那块承受着上方全部重量。所以 max⁡(wi+si)≤2×104\max(w_i+s_i) \le 2\times10^4,DP 的重量维度只需开到 2×1042\times10^4。

    复杂度

    时间 O(N⋅2×104)=2×107O(N \cdot 2\times10^4) = 2\times10^7,空间 O(2×104)O(2\times10^4)。

    参考代码

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    struct Blk { int w, s; long long v; };
    
    int main() {
        int n;
        scanf("%d", &n);
        vector<Blk> b(n);
        for (int i = 0; i < n; i++) scanf("%d %d %lld", &b[i].w, &b[i].s, &b[i].v);
        sort(b.begin(), b.end(), [](const Blk& x, const Blk& y) { return x.w + x.s < y.w + y.s; });
        const int MAXD = 20005;
        static long long f[20005];
        for (int d = 0; d < MAXD; d++) f[d] = -(1LL << 60);
        f[0] = 0;
        for (int i = 0; i < n; i++) {
            int w = b[i].w, s = b[i].s; long long v = b[i].v;
            for (int j = min(s, MAXD - 1 - w); j >= 0; j--)
                if (f[j] > -(1LL << 59)) f[j + w] = max(f[j + w], f[j] + v);
        }
        long long ans = 0;
        for (int d = 0; d < MAXD; d++) ans = max(ans, f[d]);
        return printf("%lld\n", ans), 0;
    }
    

    易错点

    1. 排序依据必须是 w+sw+s,不是 ww、不是 ss、也不是 w⋅sw\cdot s。
    2. 转移的条件是 j≤sij \le s_i(上方重量不超过坚固度),不是 j+wi≤sij + w_i \le s_i。
    3. 重量维度开到 2×1042\times10^4 即可,开到 10710^7(N×max⁡wN\times\max w)会 TLE/MLE。
    4. 价值之和可达 103×109=101210^3\times10^9 = 10^{12},必须 long long(样例 3 是 5×1095\times10^9)。
    5. viv_i 全正,答案至少为 max⁡vi\max v_i,所以 ff 的初值用极小数即可(不会选出空塔之外的坏值)。

    数据说明

    共 16 组:4 组官方样例;N=1N=1、两块相同、三块全同、单块 w=s=104w=s=10^4 的边界;N=5/10/50/100N=5/10/50/100 随机;N=1000N=1000 随机、全 w=s=1w=s=1、全 w=s=104w=s=10^4、ww 小 ss 大的构造组。

    • 1

    信息

    ID
    33
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者