P2918 [USACO08NOV] Buying Hay S(不一样的完全背包)

背包)"/>

P2918 [USACO08NOV] Buying Hay S(不一样的完全背包)

这题是个多重背包的裸题，但有一点不同，即：

多重背包的F[j]代表在不超过j磅的干草下，最小的开销

而本题的F[j]表示用(≥F[j])磅干草的最小开销

这看起来有点麻烦，但其实只需将多重背包的程序稍稍改下即可

就是可能在“背包容量”大于h的地方所用的“钱”比在h位置的少，那我们就遍历>=h,的花费找到最小值即可

ACcode:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,h,f[50005],w[105],c[105]; 
void solve() {cin>>n>>h;for(int i=1;i<=n;i++) cin>>w[i]>>c[i];for(int i=1;i<=h+5000;i++) f[i]=1e9;for(int i=1;i<=n;i++){for(int j=w[i];j<=h+5000;j++){f[j]=min(f[j],f[j-w[i]]+c[i]);}}int mmin=1<<30;for(int i=h;i<=h+5000;i++){mmin=min(mmin,f[i]);}cout<<mmin<<"\n";
}
signed main() {ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t=1;//cin>>t;while(t--) {solve();}return 0;
}

over~