[ABC145E] All-you-can-eat()

2023-02-25

题目

题目传送门

翻译

翻译

难度&重要性(1~10):5

题目来源

AtCoder

题目算法

背包dp

解题思路

设 \(dp_i\) 为最后一道菜在第 \(i\) 时吃完的最大美味值。
所以得到式子：\(dp_i=max(dp_{i-a_j}+b_j,dp_i)\ (a_j\le i)\)。
注： 每道菜先按 \(a_i\) 从小到大排序。我们要优先点食用时间短的菜，以尽量多的吃菜。

完成状态

已完成

————————

2023-02-25

题目

题目传送门

翻译

翻译

难度&重要性(1~10):5

题目来源

AtCoder

题目算法

背包dp

解题思路

设 \(dp_i\) 为最后一道菜在第 \(i\) 时吃完的最大美味值。
所以得到式子：\(dp_i=max(dp_{i-a_j}+b_j,dp_i)\ (a_j\le i)\)。
注： 每道菜先按 \(a_i\) 从小到大排序。我们要优先点食用时间短的菜，以尽量多的吃菜。

完成状态

已完成