题面:https://www.luogu.org/problemnew/show/P1417
题意
一共有$n$件食材,每件食材有三个属性,$a_i$,$b_i$和$c_i$,如果在$t$时刻完成第$i$样食材则得到$a_i-t \cdot b_i$的美味指数,用第$i$件食材做饭要花去$c_i$的时间。求T时间内能到达的最大美味指数。
解法
看上去很像一道01背包的问题。事实上一开始我也是直接按照01背包写的但只过了30%的数据点。
关键在于这里存在一个$b_i$,这会导致两个相邻的物品先放和后放导致的结果不同。如果不考虑放物品的顺序直接dp的话就有可能会出错。
考虑两个物品$i$和$j$,假设当前时间为$p$
$i$先放:$A=a_i-(p+c_i) \cdot b_i + a_j - (p+c_i+c_j)\cdot b_j$
$j$先放:$B=a_j-(p+c_j) \cdot b_j + a_i - (p+c_i+c_j)\cdot b_i$
$A>B=>c_j \cdot b_i > c_i \cdot b_j$
所以只要满足这个条件的放在前面一定结果更优。
所以,先排序,再背包,做完了。
1 |
|
v1.5.2