Uva 11137.Ingenuous Cubrency

289

题目


Description  


People in Cubeland use cubic coins. Not only the unit of currency is
called a cube but also the coins are shaped like cubes and their values
are cubes. Coins with values of all cubic numbers up to 9261(= 213
),
i.e., coins with the denominations of 1, 8, 27, . . ., up to 9261 cubes,
are available in Cubeland.
Your task is to count the number of ways to pay a given amount
using cubic coins of Cubeland. For example, there are 3 ways to pay
21 cubes: twenty one 1 cube coins, or one 8 cube coin and thirteen 1
cube coins, or two 8 cube coin and five 1 cube coins.


Input  


Input consists of lines each containing an integer amount to be paid. You may assume that all the
amounts are positive and less than 10000.


Output  


For each of the given amounts to be paid output one line containing a single integer representing the
number of ways to pay the given amount using the coins available in Cubeland.


Sample Input  


10
21
77
9999


Sample Output  


2
3
22
440022018293



题解


判断立方数组成 n 的方案数
**>背包问题 完全背包问题<**

输出需要使用 long long

代码


/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい?
エリーチカ!
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <bitset>
using namespace std;

const int INF = 0x7FFFFFFF;
const int maxn = 10005;

int v;
long long dp[maxn];

void CompletePack(int cost) {
    for(int i = cost; i <= v; i++)
        dp[i] += dp[i - cost];
}

bool Do() {
    if(!(cin >> v))
        return false;
    
    memset(dp,0,sizeof(dp));
    dp[0] = 1;

    for(int i = 1;i <= 21;i++)
        CompletePack(i*i*i);

    cout << dp[v]<<endl;

    return true;
}

int main() {
    while(Do());
    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论