题目链接:http://poj.org/problem?id=2248
分析
当搜索树的分支随深度增大得很快的时候,最适合用迭代加深。
设置一个dep限制搜索深度,一旦到达dep立刻回溯。
dep逐渐增大,逼近答案。尽管每次都会重复搜索部分分支,因为最终的dep比较小,影响不大。
这题每多一层会多很多节点,但是答案的深度比较浅,很适合用迭代加深。
代码
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#include <iostream> using namespace std; typedef long long ll; #define maxn 2000006 #define fi first #define se second #define pb push_back int n,dep; int a[105]; bool dfs(int d) { if(d > dep) { if(a[dep] == n) return 1; return 0; } bool vis[105] = {0}; for(int i=d-1;i>=1;i--) { for(int j=d-1;j>=1;j--) { if(a[i] + a[j] <= a[d - 1]) break; if(a[i] + a[j] <= n && !vis[a[i] + a[j]]) { a[d] = a[i] + a[j]; vis[a[d]] = 1; if(dfs(d + 1)) return 1; } } } return 0; } int main() { int T = 1; //scanf("%d",&T); while(T--) { while(~scanf("%d",&n)) { if(n == 0) break; dep = 1; a[1] = 1; while(!dfs(2)) { dep++; } for(int i=1;i<=dep;i++) printf("%d ",a[i]); printf("n"); } } return 0; }
最后
以上就是欣喜身影最近收集整理的关于【poj2248】 Addition Chains(迭代加深)的全部内容,更多相关【poj2248】内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复