消失之物

题意

给定一个背包和一堆物品，记(count(i,x))为没有物品(i)的前提下对于容量为(x)的背包最多能放入的物品数。求(count)矩阵。

---

思路

容斥DP，维护两个dp数组：

子状态(f[i][j])为正常背包子状态。

子状态(g[i][j])为不选(i)的子状态。

可以想到(g[i][j-w[i]])表示选择(i)的子状态，那么根据(j)与(w[i])的大小关系转移即可。

二者都能优化掉一维，此时(g)需要在更新途中输出。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T>inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}

	template<typename T>inline void write (T x) {
		if (x<0) putchar('-'),x*=-1;
		if (x>=10) write(x/10);
		putchar(x%10+'0');
	}

}

using namespace StandardIO;

namespace Project {
	
	const int N=2002;
	
	int n,m;
	int w[N];
	int f[N],g[N];

	inline void MAIN () {
		read(n),read(m);
		for (register int i=1; i<=n; ++i) read(w[i]);
		f[0]=1;
		for (register int i=1; i<=n; ++i) {
			for (register int j=m; j>=w[i]; --j) {
				f[j]=(f[j]+f[j-w[i]])%10;
			}
		}
		for (register int i=1; i<=n; ++i) {
			for (register int j=0; j<=m; ++j) {
				if (j<w[i]) g[j]=f[j];
				else g[j]=(f[j]-g[j-w[i]]+10)%10;
			}
			for (register int j=1; j<=m; ++j) write(g[j]);
			putchar('
');
		}
	}
	
}

int main () {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	Project::MAIN();
}