「一本通 1.3 例 4」Addition Chains

Addition Chains

题面

对于一个数列 \(a_1,a_2 \dots a_{m-1},a_m\) 且 \(a_1<a_2 \dots a_{m-1}<a_m\)。

数列中的一个数 \(a_k(2<k<=m)\) ,都有两个数 \(a_i,a_j(1<=i,j<k)\) 满足 \(a_i+a_j=a_k\)( \(i\) 可以等于\(j\) )。
换句话说就是 \(a_k\) 前面有两个数可以加起来等于 \(a_k\)​ 。这种数列就是加法链。

题目输入一个 \(n\) ,让你输出长度最小且以 \(n\) 结尾的加法链。

思路

  • 本题在 \(oj\) 过了,落谷貌似卡死了

  • 迭代加深优化搜索顺序

  • 不难看出题目中有最小的的字眼,并且可以确定这玩意儿可以用搜索

  • 那么迭代加深就是最好的选择,这里简单说一下迭代加深

    • 迭代加深,顾名思义,我们都知道在深搜时利用的是栈,那么官方点说就是形成了搜索树,如果你想要的答案有多解,按照树的思想就是你的多个答案分布在不同层中,要想最快得到答案,必然是去那个最近的层数。
    • 因此我们可以限制搜索层数,让其挨个搜索,减少没有用的冗杂操作。这种方法叫最优性剪枝,又称迭代加深,善于在搜索中找到最“小”答案。
  • 本题还有一个剪枝的地方,那就是优化搜索顺序,不同搜索顺序形成的搜索树大小差距倍大,

  • 题中要求最大数是 \(n\),如果抛开问题,我要求你找出可以组成 \(n\) 的数,是不是越大越好,所以要想尽快找到陪成 \(n\) 的数,那就需要从大数往前扫,

  • 依据这个特性,是不是我们需要求的 \(a_i\) 都符合以上条件,这就是需要更改搜索顺序的原因

Code

#include <iostream>//迭代加深 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

const int manx=1e6+10;
const int mamx = 1e6 + 11;
const ll mod = 2123400401301379571;
const int inf = 0x3f3f3f3f;

inline int read() {
  char c = getchar(); int x = 0, f = 1;
  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return x * f;
}
int n,a[manx],minx,ans[manx];
void dfs(int dep){//迭代加深 
	if(dep-1 > minx) return;//日常边界 
	if(a[dep-1] > n) return;//日常边界 
	if(a[dep-1] == n){
		if((dep-1) > minx) 
		return;
		minx = dep - 1;//更新 
		for(int i = 1;i <= n; i++) ans[i] = a[i];
		//else return;
	}
	else{
		for(int i = dep - 1;i >= 1; i--){//优化搜索顺序 
		if(a[dep-1] + a[i] <= n){
			a[dep] = a[dep-1] + a[i];
			dfs(dep + 1);
			a[dep] = 0;
		}
	}	
	}
} 
int main(){
	 while(1){
		n = read();
		if(n == 0) return 0;
	 	minx = 99999999;//我感觉这玩意挺神的,这个minx一是动态的,一直在更新,是的我们的答案更小 
		a[1] = 1;
	 	dfs(2);
	 	for(int i = 1;i <= minx; i++) cout<<ans[i]<<" ";
	 	cout<<endl;
	 } 
	return 0;
}


上一篇:C++编写一个加减乘除开方乘方计算器


下一篇:构建深度学习框架运行平台