【每日DP】day1 P1802 5倍经验日（别样的01背包）难度⭐★

题目链接

输入

6 8
21 52 1
21 70 5
21 48 2
14 38 3
14 36 1
14 36 2

输出

1060

一道有点意思的01背包，可以帮助理解。好久没写DP了，每天一道DP，从基础学起，正好复习一下。
这道题不同之处在于失败了（不拿走这件东西）也会有收益，所以就在正常的倒序一维01背包的基础之上，如果背包容量小于当前的物品的重量，也要加上 $lose\left[i\right]$lose[i]，以及别忘了题中的五倍经验。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4+7;
const ll mod=2147483647;
ll n,m,a[N],b[N],c[N],f[N],maxx;
int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lld %lld %lld",&a[i],&b[i],&c[i]);
    for(int i=1;i<=n;++i)
    {
        for(int j=m;j>=c[i];--j)
        {
            f[j]=max(f[j]+a[i]*5,f[j-c[i]]+b[i]*5);
        }
        for(int j=c[i]-1;j>=0;--j)
        {
            f[j]+=a[i]*5;
        }
    }
    printf("%lld\n",f[m]);
    return 0;
}

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