题解 P1802 【5倍经验日】

· · 题解

一道裸的01背包，特别简单。不过只是需要注意不用药打的人也要算在重量内

题目分析

简单的01背包，不过实在01背包的基础上加了一个小小的变化，也就是不用药打也是要算在重量内。

所以可得动态转移方程：

f[j]=max(f[j]+lost[i],f[j-use[i]]+win[i]) (当j>=use[i]时)

f[j]=f[j]+lost[i] (当j<use[i]时）

代码如下：

    //--新阶梯工作室防伪水印--
    //--By新阶梯工作室 闪现--
    #include <ctime>
    #include <cmath>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <cstdlib>
    #include <iostream>
    #include <algorithm>//头文件准备
    #define in freopen (".in","r",stdin)
    #define out freopen (".out","w",stdout)
    #define INF 2147483647
    #define UNINF -2147483648ll
    #define ch char
    #define bo bool
    #define ui unsigned int
    #define ll long long//闪现为了少打几个字符，弄了好多好多宏定义
    using namespace std;
    int n,v,c[1005];
    ll f[1005],w1[1005],w2[1005];//要用long long类型数组，要不然会爆
    inline void work();
    int main(){
        //in;out;
        work();
        return 0;
    }
    inline void work(){
        scanf ("%d %d",&n,&v);
        for (int i=1;i<=n;i++){
            scanf ("%lld %lld %d",&w1[i],&w2[i],&c[i]);
            w1[i]*=5;
            w2[i]*=5;//一开始就把5乘了，要不然容易忘记
        }
        for (int i=1;i<=n;i++){
            for (int j=v;j>=c[i];j--){//注意：01背包是从v到c[i]，不是从c[i]到v
                f[j]=max(f[j]+w1[i],f[j-c[i]]+w2[i]);//动态转移方程一
            }
            for (int j=c[i]-1;j>=0;j--){
                f[j]+=w1[i];//动态转移方程二
            } 
        }
        printf ("%lld\n",f[v]);//最后一定要用%lld输出
    }