1 限制深度
DFS 找到的第一个解未必最短;BFS 按层搜索能求最少步数,但需要保存整层状态。
如果答案较浅、分支较多,可以依次限制 DFS 的最大深度为
每一轮仍然按 DFS 的顺序访问节点,只是不能越过当前深度上限。它没有保存 BFS 的整层队列。
for (int limit = 0; ; ++limit) {
if (dfs(0, limit)) break;
}
假设每步代价均为
这只保证步数最少。若题目还要求在相同步数下比较另一项指标,不能据此立即结束整轮搜索。
2 加成序列
从
例如
它用了
2.1 枚举下一项
设已有前缀为
超过
同一前缀中,不同数对可能产生相同的
但不能只按末项做全局判重。例如前缀
2.2 翻倍剪枝
当前最大值为
因此:
这是到达目标的必要条件。即使
实现中逐次翻倍,到达
2.3 代码实现
约定 1。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
const int maxdepth = 20;
int n, path[maxdepth];
bool candidate[maxdepth][maxn];
// depth 是已做的加法次数,path[depth] 是当前最大值。
bool dfs(int depth, int limit) {
if (path[depth] == n) return true;
if (depth == limit) return false;
// 即使余下每步都把最大值翻倍,仍到不了 n,则无解。
int reach = path[depth];
for (int i = depth; i < limit && reach < n; ++i) reach *= 2;
if (reach < n) return false;
// 只对当前前缀的下一项去重;不同深度使用不同数组行。
fill(candidate[depth], candidate[depth] + n + 1, false);
for (int i = 0; i <= depth; ++i) {
for (int j = 0; j <= i; ++j) {
int x = path[i] + path[j];
if (path[depth] < x && x <= n) candidate[depth][x] = true;
}
}
// 先尝试较大的值,只改变搜索顺序,不删去较小的合法候选。
for (int x = n; x > path[depth]; --x) {
if (!candidate[depth][x]) continue;
path[depth + 1] = x;
if (dfs(depth + 1, limit)) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n && n) {
path[0] = 1;
int limit = 0;
while (!dfs(0, limit)) ++limit;
for (int i = 0; i <= limit; ++i) {
if (i) cout << ' ';
cout << path[i];
}
cout << '\n';
}
return 0;
}
candidate[depth] 每次进入当前前缀时重新清空。不同深度使用不同的行,避免递归子节点覆盖父节点尚未枚举完的候选。
数组深度取
完整题解:pcs2:加成序列。上面的程序按本文约定只输出序列;ROJ 3065 的输出格式与评测差异见题解说明。
3 埃及分数
将一个正真分数表示成若干个不同单位分数之和:
题目先要求项数
3.1 同层继续搜索
依次限制项数为
例如:
两种表示都用了
因此,递归找到解时只更新答案,再返回继续搜索。当前项数的整轮搜索结束后,若已有解,才停止增加项数。找到答案后可以增加剪枝,但不能删掉仍可能改善最大分母的分支。
3.2 枚举范围
设剩余分数为
由于分母严格递增,且
其余分母都不小于
这个上界可能包含无解候选,但不会漏解。选定
题目保证存在最大分母不超过
完整实现与边界处理见 pcs2:埃及分数。
4 代价与适用范围
迭代加深会重复搜索浅层。若每个节点稳定地产生
基础 DFS 的路径和递归栈占
它适合最浅解不深、BFS 存储压力较大,且可以有效剪枝的问题。若解可能不存在,应根据题意设置最大深度或其他终止条件,不能无限增加上限。各步代价不同时,最少步数也不再等于最小总代价。
5 相关题解
暂无相关题解