专栏文章

题解：P13659 [CERC 2020] Storage Problems

GGYHL
P13659题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mingons2
此快照首次捕获于
2025/12/02 02:07
3 个月前
此快照最后确认于
2025/12/02 02:07
3 个月前
查看原文

Description\mathscr{Description}

对于第 ii 个黑帮分子，以及每个 j(1≤j<n)j(1\le j<n)，我们要求出在储藏室中恰好有 jj 个物品，并且这些物品的总重量不超过 kk，但加上 wiw_i 后超过 kk 的不同子集的数量。

Body\mathscr{Body}

我们要求的是不包含 ii 的大小为 jj、总重为 ss 的子集数：
ansi,j=∑s=max⁡(0, K−wi+1)K\text{ans}_{i, j} = \sum_{s = \max(0,\, K-w_i+1)}^{K}
所以我们需要计算 不包含某个物品的背包方案数。
容易想到“退背包”技巧。如果我们先算出 所有物品 的背包计数 fm,sf_{m,s}（选 mm 个物品总重 ss 的方案数），那么去掉物品 ii 的方案数可以用 退背包 得到。
“退背包”定义
  • 已知包含所有物品的背包 ff。
  • 要得到不含物品 ii 的背包 gg，可以逆向进行物品 ii 的加入过程： gm,s=fm,s−gm−1,s−wi g_{m, s} = f_{m, s} - g_{m - 1, s - w_i} 这里 gg 是不含 ii 的背包，按 mm 从小到大、ss 从大到小更新。
时间复杂度为 O(N2K)\mathcal{O}(N^2K)。

Code\mathscr{Code}

CPP

/*
    author: Nimbunny
    powered by c++14
*/

#include <bits/stdc++.h>
#define endl '\n'
#define pi pair<int, int>
#define int long long
// #pragma GCC optimize(2)

using namespace std;
const double eps = 1e-6;
const int inf = 0x3f3f3f3f;
const int mod = 167772161;
const int N = 405;
int n, k, a[N], ans[N][N];
int f[N][N]; // f[i][j] 表示从所有物品中选 i 个，总重量 j 的方案数
int g[N][N]; // 临时退背包数组

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 全局背包
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = n; j >= 1; j--)
            for (int t = k; t >= a[i]; t--)
                f[j][t] = (f[j][t] + f[j - 1][t - a[i]]) % mod;
    // 对每个 i 做退背包
    for (int i = 1; i <= n; i++) {
        memcpy(g, f, sizeof f); // 复制 f 到 g
        // 退掉物品 i
        for (int j = 1; j <= n; j++)
            for (int t = a[i]; t <= k; t++)
                g[j][t] = (g[j][t] - g[j - 1][t - a[i]] + mod) % mod;
        for (int j = 1; j < n; j++) {
            int low = max(0ll, k - a[i] + 1);
            if (low > k) {
                ans[i][j] = 0;
                continue;
            }
            for (int t = low; t <= k; t++)
                ans[i][j] = (ans[i][j] + g[j][t]) % mod;
        }
    }
    for (int i = 1; i <= n; i++, cout << endl)
        for (int j = 1; j < n; j++)
            cout << ans[i][j] << " ";
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...