【Luogu】P1417烹调方案(排序01背包)

时间:2021-08-29 18:39:45

  题目链接

  对食材进行排序,重载运算符代码如下:

struct food{
    long long a,b,c;
    bool operator <(const food &a)const{
        return c*a.b<a.c*b;
    }
}s[1000];

  理由是,如果你先做当前的食材,让下一个食材等着,那下一个食材的损失就是c*a.b

  如果你先做下一个食材,让当前食材等着,当前食材损失就是a.c*b

  那当然以损失小为原则排序

  随后就是普通的01背包。代码如下:

  

#include<cstdio>
#include<algorithm>
#include<cctype>
#include<ctime>
inline long long read(){
    long long num=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')    f=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        num=num*10+ch-'0';
        ch=getchar();
    }
    return num*f;
}

struct food{
    long long a,b,c;
    bool operator <(const food &a)const{
        return c*a.b<a.c*b;
    }
}s[1000];

long long f[200010];
long long ans;
int main(){
    long long m=read(),n=read();
    for(long long i=1;i<=n;++i)    s[i].a=read();
    for(long long i=1;i<=n;++i)    s[i].b=read();
    for(long long i=1;i<=n;++i)    s[i].c=read();
    std::sort(s+1,s+n+1);
    for(long long i=1;i<=50;++i)
        for(long long j=m;j>=s[i].c;--j)
            f[j]=std::max(f[j],f[j-s[i].c]+s[i].a-j*s[i].b);
    for(long long i=0;i<=m;++i)    ans=std::max(ans,f[i]);
    printf("%lld",ans);
    return 0;
}