题解 P1802 【5倍经验日】

· · 题解

题目

这题的本质是一个01分组背包

由于只有赢与输两种,我们人为将1~n赢的一组,n+1~2n为输的一组 (回复楼上,这样做是可以的,蒟蒻之言,望巨佬注意)

我们将wi为用药数,wi+n是输的,不用要,为0

ci为赢的价值,ci+n为输的价值 这样拆分好就可以直接套用01背包了

注意:

由于有时取不到赢的价值,但一定能取到输的价值,

所以循环一定要循环到0,然后判断能否取赢的

举个简单的例子,如果他用药数比x还大,那么循环到wi就肯定跳过了,而输的价值就被吃了

上代码

#include<bits/stdc++.h>
#define ll long long  //三年oi一场空,不开longlong见祖宗!!!
using namespace std;
ll n,x,w[2222],c[2222],f[11111];
int main()
{
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        ll a,b,m;
        cin>>a>>b>>m;
        w[i]=m;
        c[i]=b;
        w[n+i]=0;
        c[n+i]=a;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=x;j>=0;j--)  //有些时候,虽然取不到赢的价值,但不能把输的价值吃了
        {
            ll a=f[j],b=f[j];
            if(j>=w[i])  //判断能否取赢的
            a=max(a,f[j-w[i]]+c[i]);
            b=max(b,f[j-w[n+i]]+c[n+i]);
            f[j]=max(a,b); //取输赢中最大值
        }
    }
    cout<<f[x]*5;   //别忘*5!!!
}