AcWing 170 加成序列【DFS 迭代加深】_windows

AcWing 170 加成序列【DFS 迭代加深】

题目描述：

满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”：

1、X[1]=1

2、X[m]=n

3、X[1]<X[2]<…<X[m-1]<X[m]

4、对于每个 kk（2≤k≤m2≤k≤m）都存在两个整数 ii 和 jj （1≤i,j≤k−11≤i,j≤k−1，ii 和 jj 可相等），使得X[k]=X[i]+X[j]。

你的任务是：给定一个整数n，找出符合上述条件的长度m最小的“加成序列”。

如果有多个满足要求的答案，只需要找出任意一个可行解。

输入格式

输入包含多组测试用例。

每组测试用例占据一行，包含一个整数n。

当输入为单行的0时，表示输入结束。

输出格式

对于每个测试用例，输出一个满足需求的整数序列，数字之间用空格隔开。

每个输出占一行。

数据范围

1≤n≤1001≤n≤100

输入样例：

输出样例：

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

分析：
迭代加深：当搜索树的节点可以很深，但是答案在非常浅的深度就可以搜到的时候，我们就可以用迭代加深进行解决。即提前设定搜索树的最大深度，一旦深度超过了设定值，就不再沿着此方向继续搜下去，而如果当前设定的最大深度没有搜索到解时，就加大最大深度，重新搜一次，直到搜到答案。

剪枝：1、优化搜索顺序，从大到小去枚举i，j，尽可能的大才能更快的逼近n。 2、排除等效冗余，枚举第u个位置上的值时，因为是枚举前面任意两个元素的和，而和可能会重复，即 2 + 4 和 1 + 5 都是6，那么以6为值向下继续搜索就会重复了，可以设定st标志数组，不去搜索重复的节点。 3、可行性剪枝，当和超过n或者和不满足序列严格单调时，就跳过。

#include <iostream>

using namespace std;

const int N = 110;

int p[N];
int n;

bool dfs(int u , int len){
    if( u == len ) return p[u - 1] == n;
    
    bool st[N] = {0};
    for(int i = u - 1 ; i >= 0  ; i --)
    {
        for(int j = i ; j >= 0  ; j --)
        {
            int t = p[i] + p[j];
            if( t > n || t <= p[u-1] ) continue;
            if( st[t] ) continue; 
            st[t] = true;
            p[u] = t;
            if( dfs( u + 1 , len) ) return true;
            
        }
    }
    
    return false;
}

int main(){
    p[0] = 1;
    while( cin >> n , n != 0)
    {
        int len = 1;
        while( true )
        {
            if( dfs( 1 , len) )  break;
            else len++;
        }
        
        for(int i = 0 ; i < len ; i ++)  printf("%d ", p[i]);
        cout <<endl;
        
    }
    
    
    return 0;
}