[luogu] P1417 烹调方案 01背包

前言

题目抽象问题还是很欠缺啊 传送门 :

思路

给你 T T T表示最大的体积 给你 n n n表示 n n n种食材

每个食材对应 3 3 3个属性 , a [ i ] , b [ i ] , c [ i ] a[i],b[i],c[i] a[i],b[i],c[i] 价值计算为 a [ i ] − b [ i ] ∗ t a[i]-b[i]*t a[i]−b[i]∗t , c [ i ] c[i] c[i]表示耗费时间

显然我们可以抽象成 01 01 01背包

但是本题最大的坑点就是 b [ i ] b[i] b[i] 影响了 01 01 01背包的计算

我们需要通过排序才可以,计算出正确的答案

c ∗ w . b < b ∗ w . c c*w.bm2 m1>m2最后解出表达式即可

CODE

const int N  = 60 ,M = 1e5+10;

struct node
{
	ll a,b,c;
	bool operator t>>n;
	for(int i=1;i>num[i].a;
	for(int i=1;i>num[i].b;
	for(int i=1;i>num[i].c;
	sort(num+1,num+1+n);
	
	for(int i=1;i=num[i].c;j -- )
		{
			f[j] = max(f[j],f[j-num[i].c] + num[i].a - j*num[i].b);
		}
		
	ll ans = 0 ;
	for(int i=1;i