神奇的四次方数

题意

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

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

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

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

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

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

思路

一句话本质：每个四次方数可以无限次使用，求凑出目标 m 的最少项数——完全背包把"价值最大化"换成"项数最小化"，max 换 min，正序枚举保持无限使用。

先看最直接的暴力：

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，并统计项数。

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

这题和经典完全背包的区别在哪？

经典完全背包求最大价值，目标是 max；这题求最少项数，目标是 min。把初始化从 0 改成 INF（除了 dp[0] = 0），把转移从 max 改成 min，其余结构完全一致。本质上就是完全背包的"最少数量"版本。

为什么每个四次方数可以重复用？

题目允许同一个四次方数取多次（例如 1^4 可以取 m 个来凑 m）。完全背包的正序枚举恰好支持"本轮更新过的状态可被本轮再次使用"的语义——dp[j - w] 如果在正序中先被更新过，本轮后续的转移就能基于已更新的值继续加 w，即实现了无限使用。

正序和倒序的本质区别是什么？

倒序（01背包）：dp[j - w] 一定来自上一轮，保证每个物品最多用一次
正序（完全背包）：dp[j - w] 可能来自本轮已经更新过的值，允许同一物品反复使用

这题需要无限使用，所以必须正序。

状态表

这张表说明状态定义：

状态	含义
`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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:13
 * update_at: 2026-08-08 23:13
 * 完全背包求最小值，dp[0]=0, dp[c]=min(dp[c], dp[c-w]+1)
 */
#include <bits/stdc++.h>
using namespace std;

const int maxn = 100005, INF = 1e9;
int m;
int dp[maxn];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> m;
    fill(dp, dp + m + 1, INF);
    dp[0] = 0;
    for (int i = 1; ; ++i) {
        int w = i * i * i * i;
        if (w > m) break;
        for (int j = w; j <= m; ++j)
            dp[j] = min(dp[j], dp[j - w] + 1);
    }
    cout << dp[m] << "\n";
    return 0;
}

复杂度

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

总结

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

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

一图流解析

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

目录

题意

思路

状态表

DP 公式

代码

复杂度

总结

一图流解析