「UVa 11137」Ingenuous Cubrency - 递推 / 背包 DP

给出一个正整数 N N \leq 1000 ),求有多少种方案把 N 表示成几个正整数的立方和的形式。

链接

UVa 11137

题解

书上的解法:用 f(i, j) 表示使用不超过 i 的整数的立方和表示数 j 的方案数。以 i 为阶段进行递推,对于每个 j,枚举新一个 i^3 项的系数 x 使 j + xi^3 \leq 1000 ,用 f(i - 1, j) 去更新 f(i, j + xi^3) 。最后 f(21, n) 即为答案。

书上在最后提到可以优化。考虑将每个立方数看做物品,将 1000 看做背包,则问题转化为:求装满背包的方案。

直接进行完全背包即可。

代码

解法一

#include <cstdio>

const int MAXN = 10000;
const int MAXI = 21;

unsigned long long f[MAXI][MAXN + 1];

inline int cube(int x) {
    return x * x * x;
}

inline void makeTable() {
    f[0][0] = 1;
    for (int i = 1; i <= MAXI; i++) {
        for (int j = 0; j <= MAXN; j++) {
            for (int x = 0, tmp; (tmp = j + x * cube(i)) <= MAXN; x++) f[i][tmp] += f[i - 1][j];
        }
    }
}

int main() {
    makeTable();

    for (int n; ~scanf("%d", &n); ) {
        printf("%llu\n", f[MAXI][n]);
    }
    return 0;
}

解法二

#include <cstdio>

const int MAXN = 10000;
const int MAXI = 21;

unsigned long long f[MAXN + 1];

inline int cube(int x) {
    return x * x * x;
}

inline void makeTable() {
    f[0] = 1;
    for (int i = 1; i <= MAXI; i++) {
        for (int c = cube(i), j = c; j <= MAXN; j++) {
            f[j] += f[j - c];
        }
    }
}

int main() {
    makeTable();

    for (int n; ~scanf("%d", &n); ) {
        printf("%llu\n", f[n]);
    }
    return 0;
}