11137 - Ingenuous Cubrency
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2078
People in Cubeland use cubic coins. Not only the unit of currency is called acube 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 1cube coins, or one 8 cube coin and thirteen 1 cube coins, or two 8 cube coin and five 1 cube coins.
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.
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
Output for sample input
2 3 22 440022018293
本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45372.htm
可以化成一维来做：dp[i] += dp[i - a[j]];//不断往更大的数上叠加。
完整代码：
/*0.015s*/
#include <cstdio>
const int maxn = 10000;
long long dp[maxn];
int a[22];
int main()
{
int i, j, n;
for (i = 1; i <= 21; ++i)
a[i] = i * i * i;
for (i = 0; i <= maxn; ++i)
dp[i] = 1;
for (j = 2; j <= 21; ++j)
for (i = a[j]; i <= maxn; ++i)
dp[i] += dp[i - a[j]];
while (~scanf("%d", &n))
printf("%lld\n", dp[n]);
return 0;
}
以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索to
， of
， The
， cube
一维
ingenuous、disingenuous、disingenuousness、disingenuously、ingenious ingenuous，以便于您获取更多的相关知识。