题解 P2918 【[USACO08NOV]Buying Hay S】
Tarantula
2020-06-06 15:52:28
## 本人新奇做法
跟各位的做法都不一样呢
此题各位大佬都是把重量当限制条件,把花费当价值的么
本蒟蒻介绍一下自己的做法,即**把重量当价值,把花费当限制条件**
然后跑完全背包,最大限制开多一点
最后一个循环+判断输出就行了
```
#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)很像欸