首页 > 题解 > bzoj3717 [PA2014]Pakowanie

bzoj3717 [PA2014]Pakowanie

Description

你有n个物品和m个包。物品有重量,且不可被分割;包也有各自的容量。要把所有物品装入包中,至少需要几个包?

Input

第一行两个整数n,m(1<=n<=24,1<=m<=100),表示物品和包的数量。
第二行有n个整数a[1],a[2],…,a[n] (1<=a[i]<=10^8),分别表示物品的重量。
第三行有m个整数c[1],c[2],…,c[m] (1<=c[i]<=10^8),分别表示包的容量。

Output

如果能够装下,输出一个整数表示最少使用包的数目。若不能全部装下,则输出NIE。

Sample Input

4 3

4 2 10 3

11 18 9

Sample Output

2

题解

这个范围一开始不敢状压,结果发现了时限90s..

首先背包按大小排个序,先装大的比较划算。

那就开两个数组,$f[s]$表示$s$时取到最少是多少,$g[s]$表示$s$时对应的最后一个包剩的最后容量。

这样对于每一个状态就可以枚举比它少一位的所有状态。可以用树状数组的那个lowbit求出来(很神奇),分情况讨论是不是能装下。

这样就可以愉快的转移了,复杂度$O(2^{24} \times 24)$,跑了26秒23333

最大收获:波兰语的“不”是“NIE”。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×