BZOJ 2287 【POJ Challenge】消失之物

题目大意

ftiasch 有 $n$ 个物品, 体积分别是 $w_1,w_2, ...,w_n$。 由于她的疏忽, 第 $i$ 个物品丢失了。 “要使用剩下的 $n-1$ 个物品装满容积为 $x$ 的背包，有几种方法呢？” -- 这是经典的问题了。她把答案记为 $count(i, x)$ ，想要得到所有$1 \le i \le n, 1 \le x \le m$的 $count(i, x)$ 表格。

这道题首先一看就是一个背包……

但是这是哪门子背包啊？

首先通过递推f[i]表示填满容量i的方案个数，之后如何求出某个东西缺失的方案个数？

直接求用这个东西的方案个数，之后再减就可以了。

设$g[i]$为去掉$x$之后剩下的物品填满i容量的方案个数。当$i \lt w[x]$的时候$g[i]=f[i]$，当$i \gt w[x]$的时候$g[i]=f[i]-g[i-w[x]]$，也就是总个数减去不使用$x$填满$i-w[x]$再用一个$x$填上剩余空间，即使用$x$的方案个数。

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,w[2010],f[2010],g[2010];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d",w+i);
    f[0]=1;
    for(int i=1;i<=n;++i)
        for(int j=m;j>=w[i];--j)
            f[j]=(f[j]+f[j-w[i]])%10;
    for(int i=1;i<=n;++i)
    {
        for(int j=0;j<w[i];++j) g[j]=f[j];
        for(int j=w[i];j<=m;++j) g[j]=(f[j]-g[j-w[i]]+10)%10;
        for(int j=1;j<=m;++j) printf("%d",g[j]);
        printf("\n");
    }
    return 0;
}