P11246 [GESP202409 六级] 小杨和整数拆分

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

题目链接：

P11246 [GESP202409 六级] 小杨和整数拆分 – 洛谷

思路：

BFS

这是一道比较好的BFS变式题目，一看题目里有最小两字，就可以模拟BFS的路径：

每次枚举当前数的所有可以减去的完全平方数，即 i*i <= x;

然后把减后的数再次入列，同时记录是第几次到达

最后先到0的数就是最少的次数

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,ans = 0;
cin >> n;
queue<int> que;
vector<int> vis(n + 1,-1);
que.push(n);
vis[n] = 0;
while(!que.empty())
{
int cx = que.front();
que.pop();
if(cx == 0){cout << vis[cx]; return 0;}
for(int i = 1;i*i <= cx;i++)
{
int ccx = cx – i*i;
if(vis[ccx] != -1) continue;
vis[ccx] = vis[cx] + 1;
que.push(ccx);
}
}
return 0;
}

DP

把题目翻译成背包

物品：1², 2², 3², 4², …（重量和价值都是它本身）
每种物品可以用无限次
问：凑出 n，最少要几件

完全背包，"求最大价值"换成"求最少件数"。

状态

dp[j] = 凑出 j，最少需要几个完全平方数

一维就够。为什么？

"还差多少钱"这件事，全在 j 里
"用了哪几个平方数"不影响后面

转移：枚举"最后一件"

凑出 j 的最后一步，一定是加了某个 k²。

dp[j] = min( dp[j – k²] + 1 ) 对所有 k² ≤ j

读法：

凑出 j 的最少件数
= "先凑出 j-k²（少用一件）的件数" + 1

为什么不重不漏？

每个方案的最后一项是唯一的——它要么是 1²，要么是 2²，要么是……

按"最后一项是谁"分类，各类互不重叠，合起来是全部。

初始值：为什么要 INF

求最小值，初始值必须比任何真答案都大。

如果初始化成 0

dp[j] = min(0, 任何正数) = 0

全表都是 0，全错。

所以要：

const int INF = 1e9;
vector<int> dp(n + 1, INF);
dp[0] = 0; // 凑 0，一件都不用

为什么不用 INT_MAX？

INT_MAX + 1 = 负的（溢出）
min(INT_MAX, 负数) = 负数

1e9 离 int 上限还有一半，加多少次都翻不上去。

顺序

dp[j] 依赖 dp[j – k²]，下标更小。

所以 j 从小到大。

而"每种物品无限次"，靠的是内层正序：

for (int j = 1; j <= n; ++j)
for (int k = 1; k*k <= j; ++k)
dp[j] = min(dp[j], dp[j – k*k] + 1);

或者写成"物品在外"：

for (int k = 1; k*k <= n; ++k) {
int w = k*k;
for (int j = w; j <= n; ++j)
dp[j] = min(dp[j], dp[j – w] + 1);
}

两种都对，因为完全背包正序时，"读到的是刚更新过的值"，正好表示"可以重复用"。

手推一小段

看几个关键的：

j=4 4 = 2² → 1
j=7 7 = 4+1+1+1 → 4 （凑不出 2 个或 3 个）
j=8 8 = 4+4 → 2
j=9 9 = 3² → 1
j=12 12 = 4+4+4 → 3
j=13 13 = 9+4 → 2
j=18 18 = 9+9 → 2

j=7 那一格值得注意：它试遍了四种最后一项，最好的也要 4 个。

代码

#include <bits/stdc++.h>
using namespace std;

int main() {
int n;
scanf("%d", &n);

const int INF = 1e9;
vector<int> dp(n + 1, INF);
dp[0] = 0;

for (int k = 1; (long long)k * k <= n; ++k) {
int w = k * k;
for (int j = w; j <= n; ++j)
dp[j] = min(dp[j], dp[j – w] + 1);
}

printf("%d\\n", dp[n]);
return 0;
}

复杂度：

代码块

物品数 √n，每个物品扫一遍容量 n
O(n√n)

n = 10⁵ 时约 3 × 10⁷，一秒内足够。

和 BFS 的对照

两者是同一个转移的两个方向：

BFS：从 n 出发，几步能踩到 0
DP ：从 0 出发，记下每个数最少几步

数学解

这个题有个纯数学的解答，这里就不多赘述了。