Problem地址:http://acm.hdu.edu.cn/showproblem.php?pid=2069

一道生成函数的题;

若对生成函数不理解，推荐看一下文章：http://www.matrix67.com/blog/archives/120

相比于普通的生成函数，她没有在每种硬币的数量是做限制，而是在硬币的总数上做了限制： Your program should be able to handle up to 100 coins.

意思就是题中所给的5种硬币的总和不能超过100;

所以在计算过程中需要对硬币的数量采取控制;

用数组c1[][],c2[][],存储系数，每个数组中一个[]填硬币总数量，一个[]填硬币总面值。

 

在敲代码时，我思考过对某些变量的顺序问题，但经过实验，在这题中，某些变量的顺序不是特别重要；

以下两个代码的思路是一样的，只是有些变量顺序是不一样的，供参考。

#include 
     
      #include 
      
       using namespace std;const int up=100;const int maxn = 250;int c1[up+10][maxn+10];int c2[up+10][maxn+10];int res[maxn+10];int coins[5]={1,5,10,25,50};int main(){    memset(c1,0,sizeof(c1));    memset(c2,0,sizeof(c2));    c1[0][0]=1;    int i,j,k,l;    for( i=0;i<5;i++ ){        for(l=0;l<=up;l++)            for( j=0;j<=maxn;j++ )                for( k=0;k*coins[i]+j<=maxn;k++ )                    if( l+k<=up )                    c2[ l+k ][ j+k*coins[i] ] += c1[l][j];        for( l=0;l<=up;l++ )            for( j=0;j<=maxn;j++ ){                c1[l][j]=c2[l][j];                c2[l][j]=0;            }    }    for(i=0;i<=maxn;i++){        res[i]=0;        for( j=0;j<=up;j++ )            res[i] += c1[j][i];    }    int T;    while(cin>>T){        cout<
       
        <
       
      
     

 

#include 
     
      #include 
      
       using namespace std;const int maxn = 250+20;const int up = 100+10;int c1[maxn][up];int c2[maxn][up];int res[maxn];int coins[5]={ 1,5,10,25,50 };int main(){    memset(c1,0,sizeof(c1));    memset(c2,0,sizeof(c2));    int i,j,k,l;    /*for( i=0;i
       
        >T ){        cout<
        
         <