hdu 1085 Holding Bin-Laden Captive! (母函数)

//给你面值为1,2,5的三种硬币固定的数目,求不能凑出的最小钱数
//G(x)=(1+x+...+x^num1)(1+x^2+...+x^2num2)(1+x^5+,,,+x^5num3),
//展开,系数不为0的数都是能够由硬币组合出来的。
# include <algorithm>
# include <string.h>
# include <stdio.h>
# include <iostream>
using namespace std;
int main()
{
int i,j,k,max1;
int c1[8100],c2[8100],a[10];
while(~scanf("%d%d%d",&a[1],&a[2],&a[5]),a[1]+a[2]+a[5])
{
max1=a[1]+a[2]*2+a[5]*5;
for(i=0;i<=8100;i++)
{
c1[i]=0;
c2[i]=0;
}
for(i=0;i<=a[1];i++)//第一种硬币
c1[i]=1;
for(i=2;i<=5;i+=3)
{
for(j=0;j<=8100;j++)
{
for(k=0;k*i+j<=8100&&k<=a[i];k++)
{
c2[j+k*i]+=c1[j];
}
}
for(j=0;j<=8100;j++)
{
c1[j]=c2[j];
c2[j]=0;
}
}
for(i=1;i<=8100;i++)
if(c1[i]==0)
{
printf("%d\n",i);
break;
} }
return 0;
}
上一篇:jquery中取消和绑定hover事件的正确方式


下一篇:手把手教windows上安装linux虚拟机及环境配置