P1679 神奇的四次方数
题目背景
在你的帮助下，v 神终于帮同学找到了最合适的大学，接下来就要通知同学了。在班级里负责联络网的是 dm 同学，于是 v 神便找到了 dm 同学，可 dm 同学正在忙于研究一道有趣的数学题，为了请 dm 出山，v 神只好请你帮忙解决这道题了。
题目描述
将一个整数 \(m\) 分解为 \(n\) 个四次方数的和的形式，要求 \(n\) 最小。例如，当 \(m=706\) 时，因为 \(706=5^4+3^4\)，所以有 \(n=2\)。可以证明此时 \(n\) 最小。
输入格式
一行，一个整数 \(m\)。
输出格式
一行，一个整数 \(n\)。
输入输出样例 #1
输入 #1
706
输出 #1
2
说明/提示
数据范围及约定
- 对于 \(30\%\) 的数据，\(m \le 5000\)；
- 对于 \(100\%\) 的数据，\(m \le 100,000\)。
观察到这是一个「用若干个数凑出指定和，并让个数最少」的问题，比较像背包模型。
样例虽然用了不同的数，但题目并没有要求“四次方数互不相同”，同一个四次方数可以使用多次，所以这是一个 完全背包问题。
我们定义状态：
- \(f[i]\)：表示「凑出和为$ i$ 时，最少需要多少个四次方数」。
先预处理出所有不超过 (m) 的四次方数，存到数组 (w) 里，即所有满足 (i^4 \le m) 的值。
初始化方面：
- \(f[0] = 0\)，表示凑出 0 不需要任何数；
- 对于 \(1 \le i \le m\)，初值设为一个很大的数，表示「暂时还凑不出来」，后面通过转移不断取最小值。
状态转移时，可以把数组 \(w\) 中的每个四次方数 \(w_k\) 看作「最后一个被选的数」。
如果当前要凑的和是 \(i\)，并且 \(i \ge w_k\)，那么先凑出和为 \(i - w_k\)，再加上这个 \(w_k\)，总共使用的四次方数个数是：
\([ f[i - w_k] + 1 ]\)
因为最后一个数可以是 \(w\) 数组里的任意一个四次方数，所以我们要在所有这些选择中取最小值，因此有转移：
\([ f[i] = \min\big(f[i],\ f[i - w_k] + 1\big) ]\)
由于每个四次方数可以被重复使用，这是一个完全背包模型。实现时，外层枚举每个四次方数 $(w_k)，内层 $(i) 从 \((w_k)\) 增加到 \((m)\)，这样可以保证同一个四次方数在同一层中被多次使用。
最终，\((f[m])\) 就表示凑出和为 \((m)\) 的最少四次方数个数，即为所求答案。
void solve()
{int m;cin >> m;vector<int> w;w.push_back(0);for(int i = 1; i * i * i * i <= m; i++){w.push_back(i * i * i * i);}vector<int> dp(m + 1, INF32);dp[0] = 0;int n = w.size();for(int i = 1; i <= n; i++){for(int j = w[i]; j <= m; j++){dp[j] = min(dp[j], dp[j - w[i]] + 1);}}cout << dp[m] << "\n";
}