注意判上界和0元购
查看原帖
注意判上界和0元购
490694
Compound_Interest楼主2022/9/25 17:09

说一下这题的坑点,希望帮助后人避坑

首先说一下为什么初始化成-INF

因为我们这个背包应该是做成价格和新鲜度刚好为下标时的答案

如果初值为0,dp数组的定义就变成价格和新鲜度小于等于下标了,与题目要求的大于等于某个新鲜度不同

这题比较坑的地方有两个

1.一个是与二维费用背包不同这题新鲜度是有可能超过询问最大值500的,但是我们的新鲜度多多益善,我们把所有新鲜度大于500的全都归结到500上处理了上界

2.这题还有cost为0的情况,最后统计ans的时候注意有0元购的情况

2022/9/25 17:09
加载中...