bzoj2287【POJ Challenge】消失之物

bzoj2287【POJ Challenge】消失之物

Description

ftiasch 有N個物品, 體積分別是W₁,W₂, ...,W_N。 由於她的疏忽, 第i個物品丟失了。 “要使用剩下的N- 1 物品裝滿容積為x的背包，有幾種方法呢？” -- 這是經典的問題了。她把答案記為Count(i, x)，想要得到所有1 <= i <= N, 1 <= x <= M的Count(i, x)表格。

Input

第1行：兩個整數N(1 ≤N≤ 2 × 10³) 和M(1 ≤M≤ 2 × 10³)，物品的數量和最大的容積。

第2行：N個整數W₁,W₂, ...,W_N, 物品的體積。

Output

一個N×M的矩陣，Count(i, x)的末位數字。

Sample Input

3 2
1 1 2

Sample Output

11
11
21

HINT

如果物品3丟失的話，只有一種方法裝滿容量是2的背包，即選擇物品1和物品2。

Source

思路很不錯的DP題，又沒有想出來做法...QAQ

f[i][j]表示前i個物品，裝滿容積為j的背包的方案數。

顯然f數組是可以用O(n^2)的DP計算出的。

g[i][j]表示不選第i個物品，裝滿容積為j的背包的方案數。

如果j

如果j≥n，則g[i][j]=f[n][j]-g[i][j-w[i]]。

可以發現f和g數組都可以用一維實現。

一開始WA了很多次，因為沒有每一步都取模。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 2005
using namespace std;
int n,m;
int f[maxn],g[maxn],w[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int main()
{
	n=read();m=read();
	F(i,1,n) w[i]=read();
	memset(f,0,sizeof(f));
	f[0]=1;
	F(i,1,n) D(j,m,w[i]) f[j]+=f[j-w[i]];
	F(i,1,n)
	{
		F(j,0,w[i]-1) g[j]=f[j];
		F(j,w[i],m) g[j]=f[j]-g[j-w[i]];
		F(j,1,m) printf("%d",g[j]%10);
		printf("\n");
	}
}