hdoj--2082<母函数>

题目链接 : http://acm.hdu.edu.cn/showproblem.php?pid=2082
题目描述：26个字母各有价值，分别是1到26；给出每个字母的个数，求单词价值不超过50 的单词有多少个；
本题的同类是换零钱：给出几种面值的硬币各有几个，求换50元钱有多少种换法；

题目要点：母函数；

母函数需要两个数组，一个数组记录当前的种类，一个数组作为临时数组辅助确定接下来有几种；

c1:1 0 0 0 0 0 0 0 00 .....(初始化)

c2:0 0 0 0 0 0 0 0 0 .....(初始化)

三层循环，第一层循环字母种类，第二曾循环使用该字母的个数；第三层循环取出该价值的字母后加到不同的价值上，生成新的价值；数组C1&C2的下标是价值，现将取出的字幕的价值总和加上之前已经取出的价值综合放到相应的c2数组；

两个数组中的值存放的是相应下标代表的价值到目前为止有几种方式；

代码如下：

 #include<stdio.h>

 #include<string.h>

 int main()

 {

     int T,i,j,z;

     int ans,c1[],c2[],ab[];

     scanf("%d",&T);

     while(T--)

     {

         for(i=;i<=;i++)

         {

             scanf("%d",&ab[i]);

         }

         memset(c1,,sizeof(c1));

         memset(c2,,sizeof(c2));

         c1[]=;

         for(i=;i<=;i++)

         {

             for(j=;j<=ab[i];j++)

             {

                 for(z=;z<;z++)

                 {

                     if(z+i*j>)//如果价值大于50 就没有必要在考虑了；

                         break;

                     c2[z+j*i]+=c1[z];//c1中存放的是种类数；将原有种类数加到现在新增的种类数上，得到一共的种类；

                 }

             }

             for(j=;j<;j++)

             {

                 c1[j]+=c2[j];       //将c2中的种类数加回c1数组中；

             }

             memset(c2,,sizeof(c2));//c2数组清零；

         }

         ans=;

         for(i=;i<;i++)

         {

             ans+=c1[i];

         }

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

hdoj--2082<母函数>

最新文章

热门文章