Differences between revisions 1 and 2
Revision 1 as of 2008-10-08 14:42:50
Size: 1712
Editor: 218
Comment:
Revision 2 as of 2008-10-08 14:44:45
Size: 2062
Editor: 218
Comment:
Deletions are marked like this. Additions are marked like this.
Line 50: Line 50:
hdu1028 hdu1085
Line 53: Line 53:
N=a[1]+a[2]+...+a[m],a[i]>0,1<=m<=N。
总共有多少种不同的方程?
4=1+3=3+1是同一种。
面值为1,2,5的硬币分别有num1,num2,num3个,
求由这些硬币不能得到的最小面值。
Line 57: Line 56:
f(x)=(1+x+x^2+...)(1+x^4+x^8+...)..(1+x^289+...)
其中x^n次方的系数就是构成总值为n的方总数。
f(x)=(1+x+x^2+...x^num1)(1+x^2+x^4+...+x^2num2)(1+x^5+...x^5num3)
其中x^n次方的系数就是构成总值为n的方总数。
Line 63: Line 62:
const int N=130; const int N=8010;
int num[3];
Line 67: Line 67:
void Poly() int Init()
Line 69: Line 69:
    scanf("%d %d %d",&num[0],&num[1],&num[2]);
    if(num[1]+num[2]+num[3]==0)
        return 0;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
Line 70: Line 75:
    for(int i=0;i<N;i++)
        for(int j=0;j<N-i;j++)
        {
    for(int i=0;i<=num[0];i++)
        a[i]=1;
    int n=num[1]+num[1];
    for(int i=0;i<=n;i+=2)
        b[i]=1;
    for(int i=0;i<=num[0];i++)
        for(int j=0;j<=n;j=j+2)
Line 74: Line 83:
        }
}
void Init()
{

    n=5*num[2];
    memset(b,0,sizeof(b));
    for(int i=0;i<=n;i+=5)
        b[i]=1;
Line 79: Line 89:
    memset(c,0,sizeof(c));
    int step;
    for(int i=0;i<N;i++)
        a[i]=1;
    for(int k=2;k<N;k++)
    {
        memset(b,0,sizeof(b));
        for(int i=0;i<N;i=i+k)
        {
            b[i]=1;
        }
        Poly();
        memcpy(a,c,sizeof(c));
    }
    int n1=num[0]+num[1]+num[1];
    for(int i=0;i<=n1;i++)
        for(int j=0;j<=n;j+=5)
            a[i+j]+=c[i]*b[j];
    return 1;
Line 96: Line 97:
    int n;
    Init();
    while(scanf("%d",&n),n)
    while(Init())
Line 100: Line 99:
        printf("%d\n",a[n]);         int k=0;
        while(1)
        {
            if(a[k]==0)
            {
                printf("%d\n",k);
                break;
            }
            k++;
        }
Line 103: Line 111:

   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 }

hdu1085 参考答案 (last edited 2008-10-08 14:44:45 by 218)

ch3n2k.com | Copyright (c) 2004-2020 czk.