【bzoj2287】[POJ Challenge]消失之物

2014年4月2日2,7552

Description

 

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

 

Input

 

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

第2行: N 个整数 W1W2, …, WN, 物品的体积。

 

Output

 

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

 

Sample Input

3 2
1 1 2

Sample Output

11
11
21

HINT

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

题解

方法:DP,f(i,j)使用前i个物品填满j的空间的方案数:

F(i,j)=f(i-1,j)+f(i-1,j-w(i)),f(0,0)=1

c(i,j)表示count(i,j),分三种情况

1,j>=w(i),c(i,j)=f(n,j)-c(i,j-w(i))即用填满j的总方案数(f(n,j))减去使用了第i个物品的方案数,其中使用第i个物品填满j的空间的方案数等于使用其余物品填满j-w(i)的空间的方案数(c(i,j-w(i)))。

3,0<j<w(i),c(i,j)=f(n,j),此时无论怎么填,都不会用到第i个物品,答案所以等于总方案数。

4,j=0,c(i,j)=1

f只要一维也可以