题解：P11069 「QMSOI R1」生熏鱼

CX_xiaoli · 2026-08-08 11:59:16 · 题解

本题解把本人思考抄题解后复盘思路的过程完整呈现了出来，希望能对大家有帮助。

题目大意

有 n 种物品，共 k 个，每种物品价值为 a_i，重量为 b_i。将物品按给定的顺序装到容量为 m 的背包中，如果一个物品装不下了，后面的物品就不能再装。你可以选择不装每种物品的第 1 次出现的物品。问最大价值。

不管题目怎么复杂，只要是有“物品”“背包容量”的，全部转换成背包问题的形式化题面，对思考一定有帮助。

状态定义

题目翻译到这里，这题肯定是背包 DP 了。那么怎么 DP 呢？初次看到这种按顺序取的问题，我们肯定是按照常规背包思路，一次 DP 直接出答案。常规地设 dp_j 为背包容量为 j 时的最大价值的想法由于 m\le10^9 而被放弃，于是我们把 dp 下标对应的量转换到其他量上。

如果把 dp 数组与 n 扯上关系，那么就设 dp_j 为丢弃 j 类物品的第一个后的最大价值。照着这条思路下去，好像跟算法标签里的“前缀和”“二分”对应上了，我们把 a_{c_i} 和 b_{c_i} 做前缀和，每次通过二分判断在哪个位置背包满……经过尝试，连个合理的状态转移都写不出来，于是放弃该方案。
如果把 dp 数组与 k 扯上关系，那么设什么呢？设 dp_j 为丢弃 j 个物品后的最大价值？不就跟上一种情况一致了吗？设 dp_j 为取到第 j 个物品的最大价值？这样就有后效性了，因为我们并不知道前面已经扔掉了哪些物品，而且也写不出状态转移，于是放弃该方案。

至此，常规方法已经全部尝试完了，依旧毫无结果。于是我们把目光转向数组的数据范围：

a_i\le10^9,b_i\le10^5+5

看着这不大的 b_i 以及不大的 n，我们能否把状态的定义往它们两个的乘积，即“消耗的背包容量”（注意与上面的“背包容量”的区别）方向靠呢？既然是消耗的背包容量，那我们就可以通过不选一些物品把消耗的容量补回来，而这个操作也会减少获得的价值，成功把容量和价值串在了一起，说明这个思路是可行的。综上分析，令 dp_j 为少选一些物品使得消耗的背包容量减少 j 的最少损失价值量。

状态转移

本题的一个难点就是状态的定义，状态转移倒不是很难。假设现在正在取第 i 个物品，并且它是第 c_i 类物品的第一次出现，则我们可以通过不取它来减少消耗的背包容量。通过取和不取两种转移方式，我们得出了总的状态转移方程：

dp_j=\min\{dp_j,dp_{j-b_{c_i}}+a_{c_i}\}

这里的数组名有点多，如果一遍没看懂可以重温一下题目里的定义。

程序过程

现在有了这个 dp 数组，我们怎么求出答案呢？首先肯定要遍历 k 个物品。而只有第一次出现的物品才可以不取，所以我们使用一个 vis 数组进行标记，来知道这类物品是不是第一次出现。如果是第一次出现，我们就可以用这一组 a_{c_i} 和 b_{c_i} 进行状态转移。每次状态转移的时间复杂度是 O(NC)（因为最多只可能不选 N 个物品，每个物品最大重量是 C），而这样的转移一共只会进行 N 次，所以这个过程的时间复杂度是 O(N^2C)。

接下来根据贪心，如果背包容量足够，我们就无脑取当前物品，直到背包剩余容量（假设为 now）小于等于 0，那么要想让背包容量回到正数，至少就需要丢弃容量为 1-now 的物品。但是可能恰好丢弃容量为 1-now 的物品并不是最优解，如果丢弃更多物品损失的价值更小，那当然是选损失价值更小的啦。所以我们需要遍历 dp_{1-now} 到 dp_{MaxJ}（用后缀最大值优化），这里的 MaxJ 就是当前所有出现过的种类的体积之和（因为每种物品只能不选一次）。而如果 1-now>MaxJ，也就是需要的容量比把所有种类都丢掉省出来的容量还要多，那就不能继续做下去了，应该退出循环。

代码实现与细节

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

#define int long long
const int M = 1e9, C = 1e5+5, N = 30, K = 2e7+5, inf = 0x3f3f3f3f3f3f3f3f;
int n, m, k, s, a[N], b[N], c[K];
bool vis[N];
int dp[N*C], mn[N*C], ans;

signed main()
{
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m >> k >> s;
    mt19937 rand(s);
    for (int i = 1; i <= n; i++)  a[i] = rand() % M + 1, b[i] = rand() % C + 1;
    for (int i = 1; i <= k; i++)  c[i] = rand() % n + 1;

    memset(dp, 0x3f, sizeof dp);
    dp[0] = 0;
    memset(mn, 0x3f, sizeof mn);
    int now = m;    // 当前剩余容量
    int sum = 0;    // 当前最多可能省出的容量，即 MaxJ
    int man = 0;    // 当前价值之和
    for (int i = 1; i <= k; i++) {
        man += a[c[i]];
        if (!vis[c[i]]) {
            sum += b[c[i]];
            vis[c[i]] = true;
            for (int j = sum; j >= b[c[i]]; j--) {
                dp[j] = min(dp[j], dp[j - b[c[i]]] + a[c[i]]);
            }
            for (int j = sum; j >= 0; j--) {    // 后缀最小值
                mn[j] = min(mn[j + 1], dp[j]);
            }
        }
        int tmp = man;
        if (now <= 0) { // 需要丢掉物品
            int l = 1 - now;    // 至少要丢掉多少容量的物品
            if (l <= sum && mn[l] < inf) {  // 如果能丢掉这么多
                tmp -= mn[l];   // 损失价值
            } else {    // 没有足够的物品来丢，结束
                break;
            }
        }
        now -= b[c[i]];
        ans = max(ans, tmp);    // 现在的 tmp 就是丢掉物品过后剩下的价值
    }

    cout << ans;

    return 0;
}

注意，这个如果 now\le0 就丢东西的过程是每次都要做的，而且丢完以后不用把剩余背包容量变为正数。这样每次算出来的 tmp 就是只看前 i 个物品的最大价值。换个方面想，如果每次都要改背包容量，那就会产生后效性，即后面丢物品的时候不知道之前有没有丢过这个物品，DP 的正确性就失效了。
记得开 long long。
边界是 dp_0=0，其他的 dp_i=+\infty，因为求的是最小值。

AC 记录，完结撒花！如果这篇题解对你有帮助，或者你觉得讲得很详细，那就给一个免费的赞吧！

管理员大大求通过！

题解：P11069 「QMSOI R1」 生熏鱼