题目链接：https://www.luogu.org/problemnew/show/P1417
复制一下别人的题解：
如果没有b[i]这个属性的话就是明显的01背包问题。
现在考虑相邻的两个物品x,y。假设现在已经耗费p的时间，那么分别列出先做x,y的代价：
a[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*by
a[y]-(p+c[y])*b[y]+a[x]-(p+c[y]+c[x])*bx
对这两个式子化简，得到①＞②的条件是c[x]*b[y]
发现只要满足这个条件的物品对(x,y)，x在y前的代价永远更优。
因此可以根据这个条件进行排序，之后就是简单的01背包了。
#include
#include
#include
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！
