P3027 [USACO10OCT]Making Money G 题解

· · 题解

题目传送门

前置知识

完全背包

完全背包模板

做法

我们做题的方法考虑完全背包。

找到每个物品的利润，我们发现就是 r_i - c_i ,花费 c_i

由此推出状态转移方程：

dp_j = \max(dp_j,dp_{j-c_i} + r_i - c_i)

代码

#include<cstdio>
using namespace std;
const int maxn=105;
int n,m,ans,c[maxn],r[maxn],dp[100005];
int max(int a,int b){if(a>b) return a;else return b;}
int main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i) scanf("%d%d",&c[i],&r[i]);
    for(register int i=1;i<=n;++i){
        for(register int j=c[i];j<=m;++j){
            dp[j]=max(dp[j],dp[j-c[i]]+r[i]-c[i]);
        }
    }
    for(register int i=1;i<=m;++i) ans=max(ans,dp[i]-i+m);
    printf("%d",ans);
}