UVa 529 Addition Chains

题目描述

题目要求构造一个加法链，即一个以111开头、以nnn结尾的严格递增序列，且序列中每个元素都是它前面某两个元素之和（这两个元素可以是同一个）。要求链的长度最短。若有多个解，输出任意一个。

输入格式

输入包含多个测试用例，每行一个整数nnn（1≤n≤100001 \le n \le 100001≤n≤10000）。输入以n=0n = 0n=0结束。

输出格式

对于每个nnn，输出一行，包含加法链中的数字，用空格分隔。

样例

输入

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

题目分析

本题的核心是使用迭代加深搜索（IDDFS\texttt{IDDFS}IDDFS）寻找最短加法链。

搜索策略

• 从111开始，依次确定下一个数。
• 每个新数必须是已有某两个数之和（可以是同一个）。
• 使用深度限制，从可能的最小深度开始递增，直到找到解。
• 剪枝：若当前深度下，剩余步数内最大可能达到的值仍小于nnn，则剪枝（即使用当前最大值每次翻倍，最大可能值 = 当前值×2剩余步数\times 2^{剩余步数}×2剩余步数）。

复杂度分析

n≤10000n \le 10000n≤10000，深度不超过202020，搜索空间可控。

代码实现

// Addition Chains// UVa ID: 529// Verdict: Accepted// Submission Date: 2016-12-21// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intpart[40]={1},bestPart[40]={1},maxDepth,n;voiddfs(intdepth){if(depth<maxDepth){for(inti=depth-1;i>=0;i--){intnext=part[depth-1]+part[i];if(next<=n){part[depth]=next;if(part[depth]==n&&maxDepth>depth){memcpy(bestPart,part,sizeof(part));maxDepth=depth;}for(intj=depth+1;j<=maxDepth;j++)next*=2;if(next>=n)dfs(depth+1);}}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);while(cin>>n,n>0){if(n==1)maxDepth=0;elsemaxDepth=20;dfs(1);for(inti=0;i<=maxDepth;i++){if(i>0)cout<<' ';cout<<bestPart[i];}cout<<'\n';}return0;}