题目分析

如果没有时间的影响的话，这就是一个简单的01背包问题。 可是有。 这个时候可以通过排序，而优先级呢，来解决。 假如此时此刻是p，有x和y两道菜，如果先做x比先做y优，则有：

a[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*b[y]>a[y]-(p+c[y])*b[y]+a[x]-(p+c[x]+c[y])*b[x] 然后随便拆一拆括号。 a[x]-p*b[x]-c[x]*b[x]+a[y]-p*b[y]-c[x]*b[y]-c[y]*b[y]>a[y]-p*b[y]-c[y]*b[y]+c[x]-p*b[x]-c[x]*b[x]-c[y]*b[x] 然后随便消除一下同类项 c[y]*b[x]>c[x]*b[y]

就是这样，喵～

代码

#include<iostream> #include<cstdio> #include<cstring> #include<iomanip> #include<algorithm> using namespace std; #define ll long long ll f[100005]; struct node{ll a,b,c;}fod[55]; ll read(){ ll w=1,q=0;char ch=' '; while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch>='0'&&ch<='9')q=(ll)q*10+ch-'0',ch=getchar(); return (ll)w*q; } int n,m;ll ans; bool cmp(node x,node y){ return x.b*y.c>y.b*x.c; } int main() { int i,j; m=read();n=read(); for(i=1;i<=n;i++)fod[i].a=read(); for(i=1;i<=n;i++)fod[i].b=read(); for(i=1;i<=n;i++)fod[i].c=read(); sort(fod+1,fod+1+n,cmp); for(i=1;i<=n;i++) for(j=m;j>=fod[i].c;j--) f[j]=max(f[j],(ll)(f[j-fod[i].c]+fod[i].a-(ll)fod[i].b*j)); for(i=1;i<=m;i++)ans=max(ans,f[i]); printf("%lld",ans); return 0; }