首页 > 代码库 > [luoguP1417] 烹调方案（背包DP）
[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{ LL a, b, c;}p[51];inline int read(){ int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; return x * f;}inline bool cmp(node x, node y){ return x.c * y.b < y.c * x.b;}int main(){ int i, j; T = read(); n = read(); for(i = 1; i <= n; i++) p[i].a = read(); for(i = 1; i <= n; i++) p[i].b = read(); for(i = 1; i <= n; i++) p[i].c = read(); std::sort(p + 1, p + n + 1, cmp); for(i = 1; i <= n; i++) for(j = T; j >= p[i].c; j--) { f[j] = max(f[j], f[j - p[i].c] + p[i].a - j * p[i].b); ans = max(ans, f[j]); } printf("%lld\n", ans); return 0;}
[luoguP1417] 烹调方案（背包DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。