【Luogu】P1417烹调方案（排序01背包）

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

struct food{

    long long a,b,c;

    bool operator <(const food &a)const{

        return c*a.b<a.c*b;

    }

}s[];

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

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

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

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

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<ctime>

inline long long read(){

    long long num=,f=;

    char ch=getchar();

    while(!isdigit(ch)){

        if(ch=='-')    f=-;

        ch=getchar();

    }

    while(isdigit(ch)){

        num=num*+ch-'';

        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[];

long long f[];

long long ans;

int main(){

    long long m=read(),n=read();

    for(long long i=;i<=n;++i)    s[i].a=read();

    for(long long i=;i<=n;++i)    s[i].b=read();

    for(long long i=;i<=n;++i)    s[i].c=read();

    std::sort(s+,s+n+);

    for(long long i=;i<=;++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=;i<=m;++i)    ans=std::max(ans,f[i]);

    printf("%lld",ans);

    return ;

}

巴特西

【Luogu】P1417烹调方案（排序01背包）

最新文章

热门文章