题解 P2918 【[USACO08NOV]Buying Hay S】

Tarantula

2020-06-06 15:52:28

Solution

## 本人新奇做法 跟各位的做法都不一样呢 此题各位大佬都是把重量当限制条件,把花费当价值的么 本蒟蒻介绍一下自己的做法,即**把重量当价值,把花费当限制条件** 然后跑完全背包,最大限制开多一点 最后一个循环+判断输出就行了 ``` #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 精卫填海](https://www.luogu.com.cn/problem/P1510)很像欸