[JOISC 2014] 挂饰 / Straps

GitHub跳转原题关系图返回列表

先把可行性化成“所选挂钩总数至少是所选挂饰数减一”，再把挂饰分成必选、必不选和可选三类，对负收益但能加挂钩的部分做 0/1 背包。

OJ: luogu

题目 ID: P4138

难度:提高+/省选-

标签:动态规划01背包分类讨论建模

日期: 2026-06-21 09:19

目录

  1. 题意
  2. 思路
    1. DP 转移方程
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

每个挂饰有两个属性：

  • A_i：它自带多少个挂钩
  • B_i：把它挂进整套挂饰后能带来的喜悦值

最终结构必须满足：

  • 最多只有一个挂饰直接挂在手机上，它相当于整棵树的根
  • 其余挂饰都要挂在某个已经选中的挂饰挂钩上
  • 挂钩可以空着，不必全部用完
  • 也可以一个挂饰都不选

要求最大化选中挂饰的喜悦值总和。

思路

先看一个可以直接验证想法的朴素解：

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

const int MAXN = 25;

int n;
int a[MAXN], b[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
    // 枚举选择哪些挂饰。若选了 k 个挂饰，只要这些挂饰的挂钩总数不少于 k-1，
    // 就一定能把它们排成一棵合法的挂饰树。
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    long long answer = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        int cnt = 0;
        int sum_a = 0;
        long long sum_b = 0;

        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                continue;
            }
            cnt++;
            sum_a += a[i];
            sum_b += b[i];
        }

        if (cnt == 0 || sum_a >= cnt - 1) {
            answer = max(answer, sum_b);
        }
    }

    cout << answer << '\n';
    return 0;
}

朴素做法只枚举选哪些挂饰，然后判断这个集合能不能排成一棵合法的挂饰树。

关键观察是：
如果选了 k 个挂饰，那么除了根以外，另外 k-1 个挂饰都要各自占用一个挂钩。
因此只要所选挂饰的挂钩总数满足：

A_{i_1}+A_{i_2}+\cdots+A_{i_k} >= k-1

这个集合就是可行的。

所以题目本质上变成：

选一个子集，使 sum(A_i) - 选中个数 + 1 >= 0，并让 sum(B_i) 最大。

把每个挂饰按 (A_i, B_i) 分类，会更清楚：

类型 处理方式 原因
A_i = 0, B_i <= 0 一定不选 不提供挂钩，收益还不正
A_i = 0, B_i > 0 留到最后按喜悦值从大到小选前若干个 每选一个都会消耗一个“可用位置”
A_i = 1, B_i < 0 一定不选 既不增加额外挂钩，又会降低答案
A_i >= 1, B_i >= 0 一定选 不会让可行性变差，而且收益非负
A_i >= 2, B_i < 0 作为背包物品考虑选不选 会亏喜悦值，但能增加额外挂钩

这里的“额外挂钩”指的是：

A_i - 1

因为一个挂饰如果不是根，它自己要先占掉一个挂钩，再把自己的 A_i 个挂钩贡献出来，所以净贡献就是 A_i-1。

于是做法就很自然了：

  1. 把 A_i >= 1, B_i >= 0 的挂饰全部选上，得到基础喜悦值和基础额外挂钩数。
  2. 把 A_i = 0, B_i > 0 的挂饰按喜悦值从大到小排序，做一个前缀和，表示“如果现在能接 k 个叶子，最佳收益是多少”。
  3. 对 A_i >= 2, B_i < 0 的挂饰做 0/1 背包：
    状态表示“额外再获得了多少个可用挂钩”，代价是损失多少喜悦值。

DP 转移方程

对一个 A_i >= 2, B_i < 0 的挂饰，令额外挂钩为 gain=A_i-1，损失为 loss=-B_i。 背包状态 dp[j] 表示得到 j 个额外挂钩时的最小损失：

dp[j+gain]=min⁡(dp[j+gain], dp[j]+loss) dp[j+gain]=\min(dp[j+gain],\ dp[j]+loss)

最后枚举额外挂钩 extra，用“基础收益 - 最小损失 + 可接正收益叶子前缀和”更新答案。 4. 枚举背包得到的额外挂钩数 extra，此时最多能接：

base + extra + 1

个 A=0 的正收益挂饰。
最后把三部分收益加起来取最大值。

其中最后的 +1 很重要，因为整棵树只需要保留一个根，它不需要消耗挂钩。

代码

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

const int MAXN = 2005;
const long long NEG_INF = -(1LL << 60);

int n;
int zero_cnt, opt_cnt;
int zero_value[MAXN];     // A=0 且 B>0 的挂饰喜悦值
int opt_cap[MAXN];        // 负收益可选挂饰增加的额外挂钩数 A-1
long long opt_joy[MAXN];  // 对应的喜悦值
long long prefix[MAXN];   // zero_value 排序后的前缀和
long long dp[MAXN], ndp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    long long base_joy = 0; // 一定选择的挂饰总喜悦值
    int base_cap = 0;       // 一定选择的挂饰总额外挂钩数

    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;

        if (a == 0) {
            // 没有挂钩的挂饰只能当叶子或唯一根。
            // 如果喜悦值不为正，就没有任何保留价值。
            if (b > 0) {
                zero_value[++zero_cnt] = b;
            }
            continue;
        }

        if (b >= 0) {
            // A>=1 且收益非负：一定值得选。
            // 它作为非根节点时，净增加 A-1 个可用挂钩。
            base_joy += b;
            base_cap += a - 1;
            continue;
        }

        if (a >= 2) {
            // 这类挂饰会亏分，但能增加额外挂钩，
            // 可能值得为了接更多正收益叶子而选择。
            opt_cap[++opt_cnt] = a - 1;
            opt_joy[opt_cnt] = b;
        }
        // a==1 且 b<0：不增加挂钩，还会降低答案，一定不选。
    }

    sort(zero_value + 1, zero_value + zero_cnt + 1, greater<int>());
    for (int i = 1; i <= zero_cnt; i++) {
        prefix[i] = prefix[i - 1] + zero_value[i];
    }

    int limit = zero_cnt;
    for (int i = 0; i <= limit; i++) {
        dp[i] = NEG_INF;
    }
    dp[0] = 0;

    // 对负收益但能增加挂钩的挂饰做 0/1 背包。
    for (int i = 1; i <= opt_cnt; i++) {
        for (int j = 0; j <= limit; j++) {
            ndp[j] = dp[j];
        }

        int w = opt_cap[i];
        if (w > limit) {
            w = limit;
        }

        for (int j = 0; j <= limit; j++) {
            if (dp[j] == NEG_INF) {
                continue;
            }
            int nj = j + w;
            if (nj > limit) {
                nj = limit;
            }
            ndp[nj] = max(ndp[nj], dp[j] + opt_joy[i]);
        }

        for (int j = 0; j <= limit; j++) {
            dp[j] = ndp[j];
        }
    }

    long long answer = 0;

    for (int extra = 0; extra <= limit; extra++) {
        if (dp[extra] == NEG_INF) {
            continue;
        }

        // 如果当前总额外挂钩数是 base_cap + extra，
        // 那么最多还能接 base_cap + extra + 1 个 A=0 的正收益挂饰。
        int can_take = base_cap + extra + 1;
        if (can_take > zero_cnt) {
            can_take = zero_cnt;
        }

        long long cur = base_joy + dp[extra] + prefix[can_take];
        answer = max(answer, cur);
    }

    cout << answer << '\n';
    return 0;
}

复杂度

设 m 是满足 A_i = 0, B_i > 0 的挂饰个数。

  • 排序复杂度是 O(mlogm)O(m log m)
  • 背包复杂度是 O(nm)O(nm)
  • 空间复杂度是 O(m)O(m)

在 n <= 2000 的范围内可以通过。

总结

这题最关键的不是直接想树怎么挂，而是先把“能否挂成一棵树”化成一个简单不等式：

sum(A_i) >= k-1

一旦化成这个条件，后面就只剩下分类讨论：

  • 哪些挂饰一定选
  • 哪些挂饰一定不选
  • 哪些挂饰需要用背包权衡

最后再把正收益叶子按价值从大到小补进去，整个模型就很清楚了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析