P11246 小杨和整数拆分 题解

· · 题解

P11246 小杨和整数拆分 题解

题意简述

小杨有一个正整数 n，小杨想将它拆分成若干完全平方数的和，同时小杨希望拆分的数量越少越好。

请你计算总和为 n 的完全平方数的最小数量。

开始解题！

这是一道很经典的广搜变式题，我们令当前状态为 \{now, dep\}，表示走到 now 需要 dep 步，然后对所有 1 \le k \le \lfloor \sqrt n \rfloor，拓展出 \{now + k ^ 2, dep + 1\} 这样的状态，并且在 now + k ^ 2 \gt n 时剪枝，在第一个 now + k ^ 2 = n 时记录一下答案，并输出。这样就完成了整个算法。

最后是时间复杂度，大家可能觉得这样的做法时间复杂度比较玄学，实则不然，我们由拉格朗日四平方和定理可得，一定会有 1 \le ans \le 4，然后对于一个状态 \{now, dep\}，其至多只有 \lfloor \sqrt n \rfloor 个前驱，所以第四层只有 n \sqrt n 个前驱，然后这个时候就是剪枝魅力时刻。在此时，大部分节点都会直接被剪掉，再加上数据比较水，所以这个时间复杂度能过，而且不玄学，最坏在 O(n \sqrt n) 到 O(n ^ 2) 之间，但是一定达不到 n ^ 2，只是因为我不会证明，可以感性理解一下。 总之能过

code : 

#include <bits/stdc++.h>
using namespace std;
int n;
struct node {
   int s, f; 
};
queue<node> q;
int bfs(int n) {
    q.push({0,0});
    while(!q.empty()) {
        node now = q.front();
        q.pop();
        int ss = now.s;
        int no = now.f;
        for(int i = 1; i * i <= n; i++) {
            ss = now.s + i * i;
            if(ss == n) return no + 1;
            if(ss > n) break;
            q.push((node){ss, no + 1});
        }
    }
    return -1;
}
int main() {
    cin >> n;
    cout << bfs(n) << endl;
}

AC record

其实从记录来看，这个代码的复杂度还是很优秀的。

做完了。