「BZOJ2287」[POJ Challenge] 消失之物

2014年4月2日3,3492

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只要一维也可以

 

说点什么

提醒
avatar
trackback

[…] 我这傻逼居然真的去写了分治背包…… 第i个物品存在的时间为[1,i−1][1,i-1]和[i+1,n][i+1,n]两个区间 然后分治…… 时间复杂度O(n2logn)O(n^2logn) 黄学长我仰慕您 […]

trackback

[…] 鎴戣繖鍌婚煎眳鐒剁湡鐨勫幓鍐欎簡鍒嗘不鑳屽寘鈥︹ 绗琲涓鐗╁搧瀛樺湪鐨勬椂闂翠负[1,i鈭1][1,i-1]鍜[i+1,n][i+1,n]涓や釜鍖洪棿 鐒跺悗鍒嗘不鈥︹ 鏃堕棿澶嶆潅搴O(n2logn)O(n^2logn) 榛勫﹂暱鎴戜话鎱曟偍 […]