[luoguP1417] 烹调方案（背包DP）
传送门
By tinylic
如果没有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]<c[y]*b[x].
发现只要满足这个条件的物品对(x,y)，x在y前的代价永远更优。
因此可以根据这个条件进行排序，之后就是简单的01背包了。
然而我看这个DP方程还不是完全的01背包，应该是 f[i] 表示到时刻 i 的最优解，且时刻 i 必须得用
代码
#include <cstdio> #include <iostream> #include <algorithm> #define N 100001 #define LL long long #define max(x, y) ((x) > (y) ? (x) : (y)) int T, n; LL ans, f[N]; struct node p[51]; inline int read() inline bool cmp(node x, node y) int main() printf("%lld\n", ans); return 0; }
下一篇：[luoguP1021] 邮票面值设计（DFS + dp）
DP
spc文件怎么看，spc文件用什么打开？
0文件怎么看，0文件用什么打开？
sparseimage文件怎么看，sparseimage文件用什么打开？
sp文件怎么看，sp文件用什么打开？
dv文件怎么看，dv文件用什么打开？
soundpack文件怎么看，soundpack文件用什么打开？
dus文件怎么看，dus文件用什么打开？
dtw文件怎么看，dtw文件用什么打开？
spdf文件怎么看，spdf文件用什么打开？
0文件怎么看，0文件用什么打开？