POJ 2248 Addition Chains (迭代加深搜索， 进阶指南)

算法竞赛进阶指南，110 页
题目意思：
求满足下列条件的数列。
•a0 = 1
•am = n
•a0 <a1 <a2 <… <am-1 <am
对于每个k（1 <= k <= m），存在两个（不一定不同的）整数i和j（0 <= i，j <= k-1），其中ak = ai + aj

注意：
1、假设序列的长度为 depth ，依次增加长度，再深搜，直到找到满足要求的序列
2、假设当前已经选好的序列为 path[1], path[2], … , path[u]
path[u + 1] 等于前 u 个数中的两个数相加 path[u + 1] = path[i] + path[j] (1 <= i, j <= u);
枚举的时候, 先枚举path[u + 1] 可能取得的大数值；
3、 用 vis[MaxN] 数组记录当前所在的额 dfs 函数中，哪些 path[u + 1] 值是已经搜过的，避免重复；

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int MaxN = 110;
int path[MaxN];
int n;

bool dfs(int u, int depth)	// u 表示当前已经枚举了多少个数
{
	if(u == depth)
	{
		return path[u] == n;	
	}
	bool vis[MaxN] = {false};
	for(int i = u; i >= 1; --i)
	{
		for(int j = i; j >= 1; --j)
		{
			int s = path[i] + path[j];
			if(s > path[u] && vis[s] == false && s <= n){
				
				path[u + 1] = path[i] + path[j];
				vis[s] = true;
				if(dfs(u + 1, depth))
				{
					return true;
				}
			}
		}
	}
	return false;
}

int main()
{
	path[1] = 1;
	while(scanf("%d", &n) != EOF && n)
	{
		int depth = 1;
		while(dfs(1, depth) == false)
		{
			++depth;
		}
		for(int i = 1; i <= depth; ++i)
		{
			printf("%d", path[i]);
			if(i < depth)
			{
				printf(" ");
			}else{
				printf("n");
			}
		}
	}
	return 0;
}

/*
5
7
12
15
77
0
*/

/*
1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77
*/

最后

以上就是跳跃小熊猫最近收集整理的关于POJ 2248 Addition Chains (迭代加深搜索， 进阶指南)的全部内容，更多相关POJ内容请搜索靠谱客的其他文章。