一个微信可以做两个网站支付/国外十大免费服务器和域名

前言

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

思路

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

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

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

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

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

$c\ast w.b<b\ast w.c$ 为什么是这个呢 ?

你可以令 $m1,m2$分别为那两个,然后令$m1>m2$最后解出表达式即可

CODE

const int N  = 60 ,M = 1e5+10;struct node
{ll a,b,c;bool operator < (const node &w){return c*w.b<b*w.c;}
}num[N];int t,n;
ll f[M];void solve()
{cin>>t>>n;for(int i=1;i<=n;i++ ) cin>>num[i].a;for(int i=1;i<=n;i++ ) cin>>num[i].b;for(int i=1;i<=n;i++ ) cin>>num[i].c;sort(num+1,num+1+n);for(int i=1;i<=n;i++)for(int j = t;j>=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<=t;i++)ans = max(ans,f[i]);cout<<ans<<endl;	}