首页 > 草药大师
头像 ddhw111
发表于 2024-05-10 02:16:37
草药大师 链接:https://ac.nowcoder.com/acm/problem/235951 来源:牛客网 做法1 因为最大容量有1e9,我们需要剪掉一些情况,对于每次物品我们只能拿一次,那么,其实也是从尾开始跑,只不过我们把从最大容量改成最大能放进的容量,如果总容量减去这一个物品的容量比原 展开全文
头像 在刷题的单身狗很开心
发表于 2023-10-09 22:20:21
题目需要对dp进行优化来减少不需要的空间和时间,在这里我们使用map去保存,使用滚动数组去代替每一种草药。 那么某一种草药对状态的影响就可以表示为去遍历map里面的每一个元素,拿这个元素的时间去加上这个时间,如果满足条件那么就可以去判断这将it->first+t这个时间下的最大值更新掉。 展开全文
头像 2023_ljd
发表于 2025-09-30 20:29:22
一种不太稳定的做法 二位大佬讲述了map优化超大背包的正解,那我就来说一下我是怎么用不太正确的复杂度卡进正解的吧。 实际上就是记忆化搜索…… 然后开了n个unordered_map,就这样简简单单的通过了哈哈哈哈哈…… 这道题的数据有待加强,毕竟这种剪枝做法真的不好说能不能通过。 AC代码: #in 展开全文

等你来战

查看全部