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~