首页 > [HEOI2013]EDEN的新背包问题

帅气小福星

发表于 2025-12-28 16:14:02

变形的多重背包,用二进制先把多重背包转化成01背包,然后再根据每次查询,跳过需要去掉的玩偶,然后开始愉快的dp,然后发现超时了.所以我们得换思路,用空间换时间,用前后缀数组来计算每次的查询,这样时间复杂度就降低了. #include<bits/stdc++.h> using namesp 展开全文

卢志成

发表于 2024-05-17 10:46:16

思路刚学完背包问题，比较熟悉。每个物品的个数有限制----> 多重背包问题用多重背包考虑的时候有两个问题，数据范围太大，考虑二进制优化；题目要求某种的物品不能使用，我们考虑如何解决。二进制优化比较简单，我们把每种物品的数量按照：1，2，4，.... , 2^n, 打包。第展开全文

杨悦聪

发表于 2023-02-11 09:45:41

相信大家都能看出这是多重背包但问题是怎么去掉某个玩偶去掉玩偶就可以单独求前面的和后面的，只需要一正一反两个背包就好了，剩下就是正常的多重背包。 AC代码 #include <bits/stdc++.h> using namespace std; int fl[100010][101 展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛