母函数问题：HDU1398Square Coins-白红宇

母函数问题：HDU1398Square Coins

阅读量：3898 次

发布时间：2019-05-23

本文共 2022 字，大约阅读时间需要 6 分钟。

Problem Description
People in Silverland use square coins. Not only they have square shapes but also their values are square numbers. Coins with values of all square numbers up to 289 (=17^2), i.e., 1-credit coins, 4-credit coins, 9-credit coins, …, and 289-credit coins, are available in Silverland.
There are four combinations of coins to pay ten credits:
ten 1-credit coins,
one 4-credit coin and six 1-credit coins,
two 4-credit coins and two 1-credit coins, and
one 9-credit coin and one 1-credit coin.
Your mission is to count the number of ways to pay a given amount using coins of Silverland.
Input
The input consists of lines each containing an integer meaning an amount to be paid, followed by a line containing a zero. You may assume that all the amounts are positive and less than 300.

Output
For each of the given amount, one line containing a single integer representing the number of combinations of coins should be output. No other characters should appear in the output.

Sample Input
2
10
30
0

Sample Output
1
4
27

题目大致意思：

硬币种类有1^2,22,3^2,42…17^2，这几种；输入n；求出能够组合成n的组合有多少种。

#include
   
    #include
    
     //#include 
     
      #include 
      
       #include
       
        using  namespace std;//HDU1398Square Coins//题意： 硬币种类有1^2,2^2,3^2,4^2...17^2，这几种；输入n；求出能够组合成n的组合有多少种。//也就是用母函数的话，第一组（x0 x1 x2...x17) 第二组的话 （x0 x2 x4 ...）int main(){
       //同理创建两个数组，一个用来存系数，一个用来存中间的值,并给他们赋初值,自我设置上限到400-1    int c[400]={
   0};    int temp[400]={
   0};    int sum[18]={
   0};    int i,j,k,n;    //首先输入数组    for(i=1;i<=17;i++){
           sum[i]=i*i;    }    //然后对第一组进行赋值,第一组可以从0到400    for(i=0;i<400;i++){
           c[i]=1;    }    //然后开始计算，从第二组开始    for(i=2;i<=17;i++){
           for(j=0;j<400;j++){
   //这个是前一项            for(k=0;k+j<400;k+=sum[i]){
                   temp[k+j]+=c[j];//这里是加等于            }        }        //然后进行还原        for(j=0;j<400;j++){
               c[j]=temp[j];            temp[j]=0;        }    }    //然后开始输入值    while(scanf("%d",&n)!=EOF&&n!=0){
           printf("%d\n",c[n]);    }}