ConanKIDの小窝

ConanKIDの小窝

题解 P2918 【[USACO08NOV]Buying Hay S】

posted on 2020-06-06 15:52:28 | under 题解 |

本人新奇做法

跟各位的做法都不一样呢

此题各位大佬都是把重量当限制条件,把花费当价值的么

本蒟蒻介绍一下自己的做法,即把重量当价值,把花费当限制条件

然后跑完全背包,最大限制开多一点

最后一个循环+判断输出就行了

#include<bits/stdc++.h>
using namespace std;
int n,m;
int w[101],val[101];
int dp[100001];//dp[i]表示以i为花费上限能买到的最大重量
int main(){
    cin>>n>>h;
    for(int i=1;i<=n;i++)
        cin>>val[i]>>w[i];//敲黑板,把重量当价值,把花费当限制条件
    for(int i=1;i<=n;i++)
        for(int j=w[i];j<=100000;j++)
            dp[j]=max(dp[j],dp[j-w[i]]+val[i]);//开大限制,跑完全背包
    for(int i=1;i<=100000;i++)
        if(dp[i]>=h){//如果以i为花费上限,可以买到比h重量多的干草
            cout<<i<<endl;//那么i就是答案了
            return 0;//拜拜了您嘞
        }
    return 0;//Happy ending~
}

话说这题貌似跟P1510 精卫填海很像欸