p4141（消失之物）

题目描述

ftiasch 有 N 个物品, 体积分别是 W1, W2, …, WN。由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N – 1 物品装满容积为 x 的背包，有几种方法呢？” — 这是经典的问题了。她把答案记为 Count(i, x) ，想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。

输入格式

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

第2行： N 个整数 W1, W2, …, WN, 物品的体积。

输出格式

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

输入输出样例

输入 #1复制

3 2

1 1 2

输出 #1复制

说明/提示

如果物品3丢失的话，只有一种方法装满容量是2的背包，即选择物品1和物品2。

题面如上。

看完会很自然地发现它是一个dp（计算方案数）

然后，如果不是漏一个的话，会非常简单（选或不选，硬算），方程式也简单得很，我这种弱鸡都能一眼看出来。

考虑一下删一个元素该怎么办。。。

首先，我们可以想到，它可能是从满的里面删掉那个物品。

经过漫长的思考，得到了以下方程式：

意思是：如果可以删的话，达到j重量不选a[i]，那我们就把选它的方案数给删去，

于是还需要处理以下全选的情况，

所以这题就没有了吧。。

坑点：

1、本题的输出非常玄学，得换连续输出两个数再换一次行，直接暴毙

2、蒟蒻看了半天没看出来要取模，最后发现是末位数字啊！！对10取模。

应该就是这样了。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int n,m;

int a[maxn];

int dp[maxn][];//µ½´ïj´óÐ¡Ê±µÄ·½°¸Êý 

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    dp[][]=dp[][]=;

    for(int i=;i<=n;i++)

    {

        for(int j=m;j>=a[i];j--)

        {

            dp[j][]+=dp[j-a[i]][];

            dp[j][]%=;

        }

    }

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=m;j++)

        {

            if(j-a[i]>=)

            dp[j][]=(dp[j][]-dp[j-a[i]][]+)%;

            else

            dp[j][]=dp[j][]%;

            printf("%d",dp[j][]);

        }

        cout<<endl;

    }

    return ;

}

（完）

巴特西