2023-06-01
题目
难度&重要性(1~10):5
题目来源
Codeforces,luogu
题目算法
01背包,dp
解题思路
这道题只需要将题面的意思转换一下就可以了。
服务员要扫物品 \(i\) 时我们是可以偷走 \(t_i\) 件物品的,一共就可以拿 \(t_i+1\) 件。
这就是我们这一件物品的“体积”了。
而因为我们必须拿或偷完 \(n\) 件,所以这里是“总体积”就最小应该为 \(n\),最大为\((t+1)_{max}+n\)。
那么,题意就变成了:
有 \(n\) 件物品,物品 \(i\) 的价值是 \(c_i\),体积为 \(t_i+1\),我们要拿一些物品使总体积大于等于 \(n\)。
现在这就是一个01背包板体了。
完成状态
已完成