前置:动态规划
最低所需知识点:01背包模型
较为基础的01背包模板题
注意初始化dp数组时全部为极大值(写INT_MAX的给我开long long啊)同时dp[0]一定要等于0!!!(不买东西还付钱的是什么鬼)
对于每次读入商品(为了表述方便 售价讲述为v 容量讲述为j)都直接从j遍历到L 更新可能的价格最小值
当然 如果j>L则价格直接从0开始叠加 同时价格赋值在L上(dp[L]=v) 这是一种节省空间的方法 在一些题目dp数组开总j会MLE的情况下可以尝试只开L+10
如果在遍历过程中出现 当前已购买的总j+当前购买j>L的情况直接赋值在L上
最后 判断时我们也可以将原本n*l(总容量)的时间复杂度讲到常数级(O1) 因为我们将所有总容量大于L的情况都归到了等于L一类中 所以只需要判断L的数值是否为初始赋值的极大值即可
如果是初始赋值的极大值 则无解 否则有解 直接输出