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

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”