bzoj - 2287

Posted by WildCow on May 18, 2018

[POJ Challenge]消失之物

Time Limit: 10MS
Memory Limit: 128 MB

Description

ftiaschN 个物品,体积分别是 $W_1, W_2, …, W_N$。 由于她的疏忽,第 $i$ 个物品丢失了。 “要使用剩下的 $N - 1$ 物品装满容积为 $x$ 的背包,有几种方法呢?” – 这是经典的问题了。她把答案记为 $Count(i, x)$,想要得到所有 $1 \leqslant i \leqslant N, 1 \leqslant x \leqslant M$ 的 $Count(i, x)$ 表格。 avater

Input

第1行:两个整数 N (1 ≤ N ≤ 2×10^3) 和 M (1 ≤ M ≤ 2×10^3),物品的数量和最大的容积。

第2行: N 个整数 $W_1, W_2, …, W_N$ 物品的体积。

Output

一个 N × M 的矩阵, $Count(i, x)$ 的末位数字。

Sample Input

3 2
1 1 2

Sample Output

11
11
21


首先吐槽一下最后是要输出末位数字,居然在 output 才说
也就等价于模 10 意义下的运算

看题解后很容易想到是 DP
直接去推不好推
考虑用容斥
对于考虑到第 $i$ 个物品体积为 $j$ 的时候,我们记为 $ans[i][j]$
如果有 $j < ma[i]$
那么第 $i$ 个物品肯定是不能选的
在这个情况下,等价于 $n$ 个物品选若干个体积恰好为 $j$ 的方案数
当 $ j\geqslant ma[i]$ 的时候
我们有 $ans[i][j] =$ $n$ 个物品选若干个体积恰好为 $j$ 的方案数 - $n$ 个物品中第 $i$ 个必选体积恰好为 $j$ 的方案数
我们接着考虑怎么求出 $n$ 个物品中第 $i$ 个必选体积恰好为 $j$ 的方案数
我们会很奇妙的发现
对于 $ans[i][j]$
$ans[i][j - ma[i]]$ 不就是$n$ 个物品中第 $i$ 个必选体积恰好为 $j$ 的方案数了吗!(拍桌)

然后对于 $n$ 个物品选若干个体积恰好为 $j$ 的方案数
设 $dp[i][j]$ 表示前 i 个物品放 j 体积有多少种放法
恩直接 01 背包就好了

然后对于 $ans$ 数组和 $dp$ 数组均可以滚动数组优化掉一维的空间


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

const int N = 2020;

int dp[N];
int ans[N];
int ma[N];

int main(int argc, char const *argv[])
{
    int n, m;

    while(scanf("%d%d", &n, &m) == 2){
        memset(dp, 0, sizeof(dp));
        memset(ans, 0, sizeof(ans));
        for(int i = 1; i <= n; i ++){
            scanf("%d", &ma[i]);
        }
        dp[0] = 1;
        for(int i = 1; i <= n; i ++){
            for(int j = m; j >= ma[i]; j --){
                dp[j] = (dp[j] + dp[j - ma[i]]) % 10;
            }
        }
        for(int i = 1; i <= n; i ++){
            for(int j = 0; j <= m; j ++){
                if(j < ma[i]){
                    ans[j] = dp[j] % 10;
                }
                else{
                    ans[j] = (dp[j] - ans[j - ma[i]] + 10) % 10;
                }
            }
            for(int j = 1; j <= m; j ++){
                printf("%d", ans[j]);
            }
            printf("\n");
        }
    }

    return 0;
}