HDU 2069 母函数

/*

注意题目要求，

1，输入0，结果1

2，方案中硬币不超过100；

与hdoj 1028不同在于有限定100，数组需要多加一维；

*/

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

#include <iostream>
#include <cstring> 
using namespace std;

int a[255][105],b[255][105];
int main()
{
    int n;
    int c[5] = {1,5,10,25,50};
    while(cin>>n)
    {
    	if(n==0)
    	{
	    	puts("1");
	    	continue;
	    }
	    memset(a,0,sizeof(a));
	    memset(b,0,sizeof(b));
        for(int i = 0; i <= min(n,100); i++)  //超过100的初始为0，否则初始化为1(存在面值1的硬币) 
        {
            a[i][i] = 1;
        }
        for(int i = 1; i <= 4; i++)  //控制硬币类型选择 
        {
        	//共五项，先将第一项和第二项乘得结果，在于第三项乘，得到结果乘第四项…… 
            for(int j = 0; j <= n; j++)    //枚举已知范围 （前面所有项结果项结果） 
            for(int k = 0; k+j <= n; k+=c[i])  //枚举新增范围（下一项 ） 
            {
            	for(int l = 0; l + k/c[i] <= 100; l++) // 硬币数量不超过100的选择 
            	{
	            	b[j+k][l+k/c[i]] += a[j][l];
	            }
            }
            for(int j = 0; j <= n; j++)    //重置 
            {
            	for(int k = 0; k <= 100; k++)
                {
                	a[j][k] = b[j][k];
					b[j][k] = 0;
                }	
            }
        }
        int sum = 0;
        for(int i = 0; i <= 100; i++)  //对不超过100硬币数的统计总和 
        	sum += a[n][i];
        cout<<sum<<endl;
    }
}