nagisa_菜鸡

分类

题解(34)

/ 注册

全部文章（共1篇）

NC14704 美味菜肴解题报告（DP(01背包)、贪心）

思路分析看到每一道菜有选和不选两种决策，我们想到了01背包。但是，和普通的01背包相比有个区别，就是做每一个决策是具有后效性的：选了i道菜会影响i+k道菜的价值，也就是说，菜的价值会和选的顺序有关。因此，我们需要利用一个贪心确定一个选择的顺序，令按照这一顺序选择答案最优。通过证明我们可以得到可以按...

每日一题背包贪心 dp

2020-04-28

0 1068