BZOJ 3717 [PA2014]Pakowanie

发布于 2017-11-03  235 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3717

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


发现有 90s,大力状压 DP。

\(f_i,g_i\) 分别表示装物品状态为 i 时的最少用包数和最后一个包的剩余空间。

暴力转移的复杂度是\(O(n*2^{n})\) 的,分析一下感觉也能过。有一个优化是发现每次只需要枚举 1,不需要枚举 0,可以用 lowbit 做到 O(1) 转移。

显然考虑所有存在的每一位,0 都不被考虑,占所有位的一半,所以时间复杂度为\(O(n*2^{n-1})\),还是很资词的。

 


一个非常弱的准退役OIER