hdu 1085 Holding Bin-Laden Captive!
问题描述：“Given some Chinese Coins (硬币) (three kinds-- 1, 2, 5), and their number is num_1, num_2 and num_5 respectively, please output the minimum value that you cannot pay with given coins.”
这是一道基本的母函数应用题。
#include<stdio.h> #include<string.h> int c1[8010],c2[8010]; int main() { int a,b,c,sum,a1[4]={2,5},i,j,k; while(scanf("%d%d%d",&a,&b,&c)!=EOF) { if(a==0&&b==0&&c==0) break; sum=a+b*2+c*5; a1[2]=b;a1[3]=c; memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); for(i=0;i<=a;i++)//初始化 c1[i]=1; int len=a; for(i=2;i<=3;i++)//i表示第i个表达式 { for(j=0;j<=len;j++)//j表示前面i-1个表达式相乘后得到的表达式的每一项的系数 for(k=0;k<=a1[i]*a1[i-2];k+=a1[i-2])//k表示第i个表达式每一项的系数 c2[k+j]+=c1[j];//将系数进行合并 len+=a1[i-2]*a1[i]; for(j=0;j<=len;j++) { c1[j]=c2[j]; c2[j]=0; } } for(i=1;i<=sum;i++) if(c1[i]==0) { printf("%d ",i); break; } if(i>sum) printf("%d ",sum+1); } return 0; }