hdu1085 参考答案

   1 /*
   2 
   3 hdu1085
   4 ymc 2008/09/25
   5 题目大意：
   6 面值为1,2,5的硬币分别有num1,num2,num3个，
   7 求由这些硬币不能得到的最小面值。
   8 解题思路：
   9 
  10 */
  11 #include <iostream>
  12 using namespace std;
  13 int n1,n2,n5;
  14 int Init()
  15 {
  16     scanf("%d %d %d",&n1,&n2,&n5);
  17     if(n1+n2+n5==0)
  18         return 0;
  19    return 1;
  20 }
  21 void Solve()
  22 {
  23     if(n1==0)
  24     {
  25         printf("1\n");
  26         return;
  27     }
  28     int n=n1+n2+n2;
  29     if(n<4)
  30     {
  31         printf("%d\n",n+1);
  32         return;
  33     }
  34     printf("%d\n",5*n5+n+1);
  35 }
  36 int main()
  37 {
  38     while(Init())
  39     {
  40         Solve();
  41     }
  42 }

   1 /*
   2 母函数
   3 hdu1085
   4 ymc 2008/09/25
   5 题目大意：
   6 面值为1,2,5的硬币分别有num1,num2,num3个，
   7 求由这些硬币不能得到的最小面值。
   8 解题思路：
   9 f(x)=(1+x+x^2+...x^num1)(1+x^2+x^4+...+x^2num2)(1+x^5+...x^5num3)
  10 其中x^n次方的系数就是构成总值为n的方法总数。
  11 具体参考 生成函数,也叫母函数。
  12 */
  13 #include <iostream>
  14 using namespace std;
  15 const int N=8010;
  16 int num[3];
  17 int a[N];
  18 int b[N];
  19 int c[N];
  20 int Init()
  21 {
  22     scanf("%d %d %d",&num[0],&num[1],&num[2]);
  23     if(num[1]+num[2]+num[3]==0)
  24         return 0;
  25     memset(a,0,sizeof(a));
  26     memset(b,0,sizeof(b));
  27     memset(c,0,sizeof(c));
  28     for(int i=0;i<=num[0];i++)
  29         a[i]=1;
  30     int n=num[1]+num[1];
  31     for(int i=0;i<=n;i+=2)
  32         b[i]=1;
  33     for(int i=0;i<=num[0];i++)
  34         for(int j=0;j<=n;j=j+2)
  35             c[i+j]+=a[i]*b[j];
  36 
  37     n=5*num[2];
  38     memset(b,0,sizeof(b));
  39     for(int i=0;i<=n;i+=5)
  40         b[i]=1;
  41     memset(a,0,sizeof(a));
  42     int n1=num[0]+num[1]+num[1];
  43     for(int i=0;i<=n1;i++)
  44         for(int j=0;j<=n;j+=5)
  45             a[i+j]+=c[i]*b[j];
  46     return 1;
  47 }
  48 int main()
  49 {
  50     while(Init())
  51     {
  52         int k=0;
  53         while(1)
  54         {
  55             if(a[k]==0)
  56             {
  57                 printf("%d\n",k);
  58                 break;
  59             }
  60             k++;
  61         }
  62     }
  63 }