P1679 神奇的四次方数

P1679 神奇的四次方数

题目链接：P1679 神奇的四次方数 - 洛谷

题目描述

将一个整数 $m$ 分解为 $n$ 个四次方数的和的形式，要求 $n$ 最小。例如，当 $m = 706$ 时，因为 $706 = 5^4 + 3^4$，所以有 $n = 2$。可以证明此时 $n$ 最小。

100 分解法

完全背包变形

观察数据范围 $m \leq 100,000$。

$20^4 > 100,000$，所以四次方数的范围为 $1 \sim 20$。

$dp_{i,j}$ 表示用前 $i$ 种数（$1 \sim 20$）配成 $j$ 的最少个数。

初始化：

• $w_i = i^4$
• $dp_{i,j} = \text{INF}$
• $dp_{0,0} = 0$

状态转移方程：

$dp_{i,j} = \min(dp_{i-1,j}, dp_{i,j-w_i} + 1)$

#include <bits/stdc++.h>
using namespace std;const int N = 21, M = 1e5 + 5;
int m, w[N], dp[N][M];int main() {cin >> m;for (int i = 1; i <= 20; i++)w[i] = i * i * i * i;memset(dp, 0x3f, sizeof(dp));dp[0][0] = 0;for (int i = 1; i <= 20; i++) {for (int j = 0; j <= m; j++) {dp[i][j] = dp[i - 1][j];if (j >= w[i])dp[i][j] = min(dp[i][j], dp[i][j - w[i]] + 1);}}cout << dp[20][m];return 0;
}

拓展知识

若将四次方数改为平方数同理，有拉格朗日四平方和定理：

每个正整数均可表示为四个整数的平方和。