P2918 [USACO08NOV]买干草Buying Hay
显然的完全背包
设$f[i]$为买$i$磅干草的最小代价
搞搞完全背包即可
注意到最后可能买的干草超出范围，但是价格可能更低。
于是我们的背包处理到$m+maxP$即可（本题$P_{i}<=5000$）
end.
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define re register 5 using namespace std; 6 int min(int a,int b){return a<b?a:b;} 7 #define P 5000 8 int n,m,f[55005],a,b,ans; 9 int main(){ 10 memset(f,127,sizeof(f));ans=f[0];f[0]=0; 11 scanf("%d%d",&n,&m); 12 for(re int i=1;i<=n;++i){ 13 scanf("%d%d",&a,&b); 14 for(re int j=a;j<=m+P;++j)//处理到m+maxP 15 f[j]=min(f[j],f[j-a]+b); 16 } 17 for(re int j=m+P;j>=m;--j) ans=min(ans,f[j]);//在超出的范围中找最小值 18 printf("%d",ans); 19 return 0; 20 }