hdu 2069 1 5 10 25 50 这几种硬币 一共100个(母函数)

时间：2023-03-27 08:15:44

题意： 有50 25 10 5 1 的硬币 一共最多有100枚 输入n输出有多少种表示方法

Sample Input
11
26

Sample Output
4
13

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <string>

 # include <cmath>

 # include <queue>

 # include <list>

 # define LL long long

 using namespace std ;

 int c1[][],c2[][];

 int ans[] ;

 int w[]={,,,,,};

 void Init(){

     memset(c1,,sizeof(c1));

     memset(c2,,sizeof(c2));

     c1[][]=;

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

     {

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

             for(int k=;j+k*w[i]<=;k++)

                 for(int p=;k+p<=;p++)

                     c2[j+k*w[i]][p+k]+=c1[j][p];

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

             for(int p=;p<=;p++)

             {

                 c1[j][p]=c2[j][p];

                 c2[j][p]=;

             }

     }

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

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

             ans[i]+=c1[i][j]; //c1[11][3]表示这个方案 是用3枚硬币组成11的

     ans[]=;

 }

 int main()

 {

     int n;

     Init();

     while(~scanf("%d",&n))

     {

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

     }

     return ;

 }

相关文章