首页 > 代码库 > hdu 1085 Holding Bin-Laden Captive!（母函数）
hdu 1085 Holding Bin-Laden Captive!（母函数）
题意：
硬币有三种值：1，2，5。各自的数量分别是n1,n2,n5。
问无法凑出的最小币值是多少。
思路：
用背包DP好解。
不过俺用母函数做。其实二者的思路在本质上是一样的，，，，
看代码，，
代码：
int n1,n2,n5;bool a[8005], b[8005];int main(){ while(scanf("%d%d%d",&n1,&n2,&n5)!=EOF,n1||n2||n5){ mem(a,false); a[0]=true; int maxs=n1+2*n2+5*n5; mem(b,false); rep(i,0,maxs){ if(a[i]==true){ rep(k,0,n1){ if(i+k<=maxs){ b[i+k]=true; } } } } rep(i,0,maxs) a[i]=b[i]; mem(b,false); rep(i,0,maxs){ if(a[i]==true){ rep(k,0,n2){ if(i+2*k<=maxs){ b[i+2*k]=true; } } } } rep(i,0,maxs) a[i]=b[i]; mem(b,false); rep(i,0,maxs){ if(a[i]==true){ rep(k,0,n5){ if(i+5*k<=maxs){ b[i+5*k]=true; } } } } rep(i,0,maxs) a[i]=b[i]; int ans=-1; rep(i,0,maxs){ if(a[i]==false){ ans=i; break; } } if(ans==-1) ans=maxs+1; printf("%d\n",ans); } return 0;}
hdu 1085 Holding Bin-Laden Captive!（母函数）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。