ShineEternal的小书屋

ShineEternal的小书屋

https://blog.csdn.net/kkkksc03

题解 P3027 【[USACO10OCT]赚钱Making Money】

posted on 2019-10-26 19:48:21 | under 题解 |

$My\ blog$

solution:

完全背包的好题。

每次的价值是利润(r-c),花费是c

然后套板子就行了

#include<cstdio>
#include<algorithm>
using namespace std;
int f[100005],a[105],c[105];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int r;
        scanf("%d%d",&c[i],&r);
        a[i]=r-c[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=c[i];j<=m;j++)
        {
            f[j]=max(f[j],f[j-c[i]]+a[i]);
        }
    }
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        ans=max(ans,f[i]-i+m);
    }
    printf("%d\n",ans);
    return 0;
}