P1417 烹调方案

每件物品只有一个，很明显是01背包，但是价值的转换方式不同，是要求 a i − t ∗ b i a_i-t*b_i ai​−t∗bi​ 尽可能最大。普通的01背包的价值是不变的，而这一道题目中的价值是随着所选物品的顺序有所改变，所以应该按照题意排序，并用 maxn去找最大的答案，因为答案不一定是 f [ t ] f[t] f[t]。

还有就是常开 l o n g l o n g long long longlong 是个好习惯。

那么现在就看如何排序就好，对于每一件物品，影响价值的因素是 b 和 t，t是由 c 叠加而来，所以按照a.c*b.b<b.c*a.b来排序即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100007;
const ll mod=100000000;
struct node
{
    ll a,b,c;
    bool operator<(const node &t)const
   {
       return c*t.b<t.c*b;
   }
}a[N];
ll n,m,f[N],maxn;
int main()
{
    scanf("%lld %lld",&m,&n);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i].a);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i].b);
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i].c);
    sort(a+1,a+1+n);
    for(ll i=1;i<=n;++i)
        for(ll j=m;j>=a[i].c;--j)
            f[j]=max(f[j],f[j-a[i].c]+a[i].a-a[i].b*j);
    for(ll i=1;i<=m;++i)
        maxn=max(maxn,f[i]);
    printf("%lld\n",maxn);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜