北邮ACM2017网预 Square Coins-动态规划

题目

Artoria, also known as Saber-chan, was born into a time of chaos and war that began with the demise of the Roman empire. Somewhere in the far east, people in Utopia know nothing about war or conflicts. They live in peace for quite a long time and developed a strange currency system. In particular, they use square coins. Not only have they square shapes but also their values are square integers. Coins with values of all square numbers up to 289 (=172), i.e., 1-credit coins, 4-credit coins, 9-credit coins, …, and 289-credit coins, are available in Utopia.

According to the Utopia currency system, 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 Utopia. The answer may be very big, please output the answer module 1000000009.

input

The input begins with a line containing a single integer T(1≤T≤2000), indicating the number of test cases. Each of the next T lines each containing an integer meaning an amount to be paid. You may assume that all the amounts are positive and less than 2000.

output

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

sample
input

2
10
30

output

4
27

分析

一共有17种面值的硬币，个数不限，给定一个数值n，给出有多少种组合方式

利用动态规划的思想，可以预先计算好组成n的组合方式

dp[i+coin[j]] = dp[i+coin[j]]+dp[i]

代码

#include <iostream>
#include <stdlib.h>
#include <cstring>
#include <stdio.h>
#include <vector>
using namespace std;
int dp[2005];
 
int main()
{
    vector<int> result;
    memset(dp, 0, 2005);
    dp[0] = 1;
    for (int i = 1; i <= 17; i++) {
        for (int j = 0; j < 2005; j++) {
            dp[j + i*i] = (dp[j + i*i] + dp[j])% 1000000009;
        }
    }
    int N;
    scanf("%d", &N);
    while (N) {
        int n;
        scanf("%d", &n);
        printf("%d\n",dp[n]);
        N--;
    }
     
    //system("pause");
    return 0;
}