UVA11137(立方数之和)
题意：
给你一个n(<=10000),问他如果由立方数之和组成，那么有多少种方法？
思路：
一个地推公式，d[i][j] 表示用不大于i的数字去组合j这个数字有多少种方法，因为n<=10000所以i最大是21，最后答案就是d[21][n],地推公式是
d[i][j] = d[i-1][j] + d[i][j-i*i*i];
可以这样理解，d[i-1][j]好说，就是不用当前这个数，d[i][j-i*i*i]表示的是用i，同时
for(i = j ;j <= n ;j ++)正着跑还能是的i用多次，想起了01和完全背包。
#include<stdio.h>
#include<string.h>
long long d[23][10005];
void solve()
{
for(int i = 1 ;i <= 10000 ;i ++)
d[1][i] = 1;
for(int i = 1 ;i <= 21 ;i ++)
d[i][0] = 1;
for(int i = 2 ;i <= 21 ;i ++)
for(int j = 1 ;j <= 10000 ;j ++)
{
d[i][j] = d[i-1][j];
if(j - i * i * i >= 0)
d[i][j] += d[i][j-i*i*i];
}
}
int main()
{
int n;
solve();
while(~scanf("%d" ,&n))
{
printf("%lld " ,d[21][n]);
}
return 0;
}
给你一个n(<=10000),问他如果由立方数之和组成，那么有多少种方法？
思路：
一个地推公式，d[i][j] 表示用不大于i的数字去组合j这个数字有多少种方法，因为n<=10000所以i最大是21，最后答案就是d[21][n],地推公式是
d[i][j] = d[i-1][j] + d[i][j-i*i*i];
可以这样理解，d[i-1][j]好说，就是不用当前这个数，d[i][j-i*i*i]表示的是用i，同时
for(i = j ;j <= n ;j ++)正着跑还能是的i用多次，想起了01和完全背包。
#include<stdio.h>
#include<string.h>
long long d[23][10005];
void solve()
{
for(int i = 1 ;i <= 10000 ;i ++)
d[1][i] = 1;
for(int i = 1 ;i <= 21 ;i ++)
d[i][0] = 1;
for(int i = 2 ;i <= 21 ;i ++)
for(int j = 1 ;j <= 10000 ;j ++)
{
d[i][j] = d[i-1][j];
if(j - i * i * i >= 0)
d[i][j] += d[i][j-i*i*i];
}
}
int main()
{
int n;
solve();
while(~scanf("%d" ,&n))
{
printf("%lld " ,d[21][n]);
}
return 0;
}