444

# 题目

## 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.

10
21
77
9999

2
3
22
440022018293

# 题解

**>背包问题 完全背包问题<**

# 代码

/*
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;
}

• 点击查看/关闭被识别为广告的评论