背包)"/>
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~
更多推荐
P2918 [USACO08NOV] Buying Hay S(不一样的完全背包)
发布评论