BZOJ 3717 [PA2014]Pakowanie


题目链接: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})\),还是很资词的。

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3717 [PA2014]Pakowanie


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,