SDUT-4534-肝是不可能肝的(完全背包)

题目链接

http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2956/pid/4534

解题思路

dp[i]代表体力剩余 i 时所能获得的最大收益。
首先不考虑加体力跑一遍完全背包,然后再让
dp[j+100]=max(dp[j],dp[j+100]);
来实现加体力100
加完体力后再跑一遍完全背包获得结果。

代码

#include <bits/stdc++.h>
const int maxn=333;
using namespace std;
int dp[maxn],w[maxn],c[maxn];
int main() {
    int n;
    cin>>n;
    memset(dp,-0x3f3f3f3f,sizeof(dp));
    //dp[i],剩余 i 体力时的最大收益
    dp[0]=0;
    int ans=-0x3f3f3f3f;
    for(int i=1;i<=n;i++){
        int m;
        cin>>m;
        for(int j=1;j<=m;j++){
            cin>>c[j]>>w[j];
        }
        for(int j=1;j<=m;j++){
            for(int k=200;k>=0;k--){
                dp[k]=max(dp[k],dp[k+c[j]]+w[j]);//由体力多向体力少转移。
            }
        }
        for(int j=0;j<=99;j++){//加体力
            dp[j+100]=max(dp[j],dp[j+100]);
        }
        for(int j=1;j<=m;j++){//加体力后重新计算
            for(int k=200;k>=0;k--){
                dp[k]=max(dp[k],dp[k+c[j]]+w[j]);
                ans=max(ans,dp[k]);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注