AcWing 170. 加成序列
原题链接
简单
作者:
Anoxia_3
,
2021-05-16 13:05:28
,
所有人可见
,
阅读 287
/*
迭代加深:
在搜索的时候,搜索树中有些错误的节点可能会特别深,从而浪费很多时间,但是实际上它的合法方案在一个比较浅的位置。
迭代加深是一层一层搜,但是有别于bfs,bfs是每次把一层的点全部搜完,宽搜有一个队列,,空间是指数级别。
迭代加深会定义一个层数上限,如果当前的深度超过层数上限,直接return,本质是dfs,O(h)。
适合:某些分支层数很深,但是答案在比较浅的深度。
剪枝:
优化搜索顺序:优先枚举较大的数
排除等效冗余:一组内两个数的和可能会出现重复,开一个bool数组
*/
#include <iostream>
using namespace std;
const int N = 110;
int n;
int path[N];
bool dfs(int u , int depth)
{
if(u > depth) return false;
if(path[u - 1] == n) return true;
bool st[N] = {0};//st只是在第u层用来判重的,所以st不需要恢复
for(int i = u - 1 ; i >= 0 ; i--)
for(int j = i ; j >= 0 ; j--)
{
int s = path[i] + path[j];
if(s > n || st[s] || s <= path[u - 1]) continue;
st[s] = true;
path[u] = s;//记录第u层的节点
if(dfs(u + 1 , depth)) return true;
}
return false;
}
int main()
{
path[0] = 1;//起点是第0层,是1
while(cin >> n , n)
{
int depth = 1;
while(!dfs(1 , depth)) depth++;//从小到大枚举搜索深度
for(int i = 0 ; i < depth ; i++)
cout << path[i] << ' ';
cout << endl;
}
return 0;
}