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

发表于 | 分类于

给出一个正整数 （），求有多少种方案把 表示成几个正整数的立方和的形式。

链接

UVa 11137

题解

书上的解法：用 表示使用不超过 的整数的立方和表示数 的方案数。以 i 为阶段进行递推，对于每个 j，枚举新一个 项的系数 使 ，用 去更新 。最后 即为答案。

书上在最后提到可以优化。考虑将每个立方数看做物品，将 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;
}