神奇的四次方数

题意

给定一个整数 m，把它表示成若干个四次方数之和。

要求使用的四次方数个数最少。

例如 706 = 5^4 + 3^4，所以答案是 2。

这张表把题目翻译成了背包模型：

原题对象	背包含义
一个四次方数 `i^4`	一个可以重复使用的物品
选择一个四次方数	物品重量增加 `i^4`
目标	凑出总和 `m`
评价标准	使用的项数最少

从这里可以看出，本题是一个“最少项数”的完全背包。

思路

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。

const int INF = 1e9;

int m;
vector<int> pows;
vector<int> choose_count; // choose_count[i] 表示第 i 种四次方数取多少个
int answer = INF;

int calc_sum() {
    int sum = 0;
    for (int i = 0; i < (int)pows.size(); i++) {
        sum += choose_count[i] * pows[i];
    }
    return sum;
}

int calc_count() {
    int cnt = 0;
    for (int i = 0; i < (int)pows.size(); i++) {
        cnt += choose_count[i];
    }
    return cnt;
}

// 依次枚举每种四次方数要用多少个，叶子节点统一检查。
void dfs_choose(int dep) {
    if (dep == (int)pows.size()) {
        if (calc_sum() == m) {
            int value = calc_count();
            if (answer > value) answer = value;
        }
        return;
    }

    int w = pows[dep];
    int limit = m / w;
    for (int cnt = 0; cnt <= limit; cnt++) {
        choose_count[dep] = cnt;
        dfs_choose(dep + 1);
    }
}

void read_input() {
    cin >> m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    for (int i = 1; ; i++) {
        long long x = 1LL * i * i * i * i;
        if (x > m) {
            break;
        }
        pows.push_back((int)x);
    }

    choose_count.assign(pows.size(), 0);
    dfs_choose(0);
    cout << answer << '\n';

    return 0;
}

brute.cpp 把每种四次方数取多少个看成一层选择：choose_count[i] 表示第 i 种四次方数取几个。递归先生成完整计数序列，叶子节点再检查能不能刚好凑出 m，并统计项数。

这个做法显然正确，但复杂度很高，只适合小数据验证。

关键观察是：每种四次方数都可以重复使用，而且我们要最小化“项数”。

所以设：

dp[j] 表示凑出 j 的最少四次方数个数

这张表说明状态定义：

状态	含义
`dp[j]`	凑出 `j` 的最少四次方数个数

初始化时：

dp[0] = 0
其他位置先设成 INF

处理每个四次方数 w 时，因为它可以重复使用，所以容量必须正序枚举：

dp[j] = min(dp[j], dp[j - w] + 1)

正序枚举时，dp[j - w] 可能已经在本轮被更新过，这就允许同一种四次方数反复使用。

最后输出 dp[m] 即可。

DP 公式

设 $dp_j$ 表示凑出 $j$ 的最少四次方数个数。初始化：

dp_0=0,\quad dp_j=+\infty\ (j>0)

对于每个四次方数 $w=x^4$ ，做完全背包转移：

dp_j=\min(dp_j,\ dp_{j-w}+1)

容量正序枚举，最终答案为：

dp_m

公式解释：每个四次方数都可以重复使用，状态值是凑出目标数所需的最少项数。选一个四次方数后，数量在 dp_{j-w} 基础上加一。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#include <bits/stdc++.h>
using namespace std;

const int MAXM = 100005;
const int INF = 1e9;

int m;
vector<int> pows;      // 所有不超过 m 的四次方数
vector<int> dp;        // dp[j] 表示凑出 j 的最少四次方数个数

void read_input() {
    cin >> m;
}

void solve() {
    for (int i = 1; ; i++) {
        long long x = 1LL * i * i * i * i;
        if (x > m) {
            break;
        }
        pows.push_back((int)x);
    }

    dp.assign(m + 1, INF);
    dp[0] = 0;

    for (int i = 0; i < (int)pows.size(); i++) {
        int w = pows[i];
        // 完全背包：同一种四次方数可以重复使用，所以容量正序枚举。
        for (int j = w; j <= m; j++) {
            if (dp[j - w] + 1 < dp[j]) {
                dp[j] = dp[j - w] + 1;
            }
        }
    }

    cout << dp[m] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(m \sqrt[4]{m})$
空间复杂度： $O(m)$

总结

这题和完全背包的经典模板完全同型，只是目标从“最大价值”变成了“最少项数”。

以后看到“每种对象可重复使用、要把一个数拆成若干份、并且要求份数最少”这类条件时，就可以优先往完全背包上想。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析