首页 > 代码库 > bzoj1618[Usaco2008 Nov]Buying Hay 购买干草*
bzoj1618[Usaco2008 Nov]Buying Hay 购买干草*
bzoj1618[Usaco2008 Nov]Buying Hay 购买干草
题意：
n种物品，每种无限个，重量为pi，费用为ci，要求总重量超过h的前提费用最小。求最小费用。n≤100，m≤50000。
题解：
dp。f[i][j]=min(f[i-1][j],f[i][j-p[i]]+c[i])，边界f[0][0]=0，f[0][1..m+mx]=INF。最后在f[n][m..m+mx]中找一个最小的。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 60010 7 #define INF 0x3fffffff 8 using namespace std; 9 10 inline int read(){11 char ch=getchar(); int f=1,x=0;12 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}13 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();14 return f*x;15 }16 int f[2][maxn],mx,n,m,p[maxn],c[maxn],x,y;17 int main(){18 n=read(); m=read(); inc(i,1,n)p[i]=read(),c[i]=read(),mx=max(mx,p[i]);19 x=0; y=1; inc(i,0,m+mx)f[x][i]=INF; f[x][0]=0;20 inc(i,1,n){21 inc(j,0,m+mx)f[y][j]=f[x][j]; 22 inc(j,p[i],m+mx)f[y][j]=min(f[y][j],f[y][j-p[i]]+c[i]);23 swap(x,y);24 }25 y=INF; inc(i,m,m+mx)y=min(y,f[x][i]); printf("%d",y); return 0;26 }
20160918
bzoj1618[Usaco2008 Nov]Buying Hay 购买干草*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。