题目:https://www.luogu.org/problemnew/show/P1417
与01背包的不同在于价值受时间影响。
对第i个物品的遍历有一个先后顺序,在01背包里顺序不影响,但此时顺序会影响。
所以可以考虑对遍历的顺序排序。因为排序时会把每一个都和其余所有比较一番,所以考虑好排序的条件就能保证排序之后就可以01背包了。
排序时只有两种情况:x在y前 和 y在x前。考虑这两种的不同之处在于x在y前时多减了x.c*y.b,y在x前时多减了y.c*x.b,故把减得少的排在前面。
关键在于这个排序的考量!不是简单地按c的大小排,也不是把a也带上然后如何地算一番,而是考虑 x在y前 和 y在x前 这两种情况的不同点!
因为 x在y前 和 y在x前 两种情况中的x的值和y的值也是变化的!
最后注意输入是一行一行的。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,t; long long d[100005],mx; struct Node{ long long a,b,c; }v[55]; bool cmp(Node x,Node y){return y.b*x.c<x.b*y.c;} int main() { scanf("%d%d",&t,&n); for(int i=1;i<=n;i++) scanf("%lld",&v[i].a); for(int i=1;i<=n;i++) scanf("%lld",&v[i].b); for(int i=1;i<=n;i++) scanf("%lld",&v[i].c); sort(v+1,v+n+1,cmp); for(int i=1;i<=n;i++) for(int j=t;j>=v[i].c;j--) d[j]=max(d[j],d[j-v[i].c]+v[i].a-j*v[i].b); for(int i=1;i<=t;i++) if(d[i]>mx)mx=d[i]; printf("%lld",mx); return 0; }