题目连接:11137 - Ingenuous Cubrency
题目大意:由21种规模的立方体(r 1~21),现在给出一个体积, 要求计算可以用多少种方式组成。
解题思路:完全背包, 和uva674是一样的, 只是这里的体积是r ^ 3。
#include <stdio.h>
#include <string.h>
const int N = 10005;
long long dp[N]; void Init() {
int t;
dp[0] = 1;
for (int i = 1; i <= 21; i++) {
t = i * i * i;
for (int j = t; j < N; j++)
dp[j] += dp[j - t];
}
} int main() {
Init();
int n;
while (scanf("%d", &n) == 1) {
printf("%lld\n", dp[n]);
}
return 0;
}