[UVA 529] Addition Chains (迭代加深搜索)-CSDN博客

本文链接：https://blog.csdn.net/sio__five/article/details/18996127

题目链接：http://acm.bnu.edu.cn/bnuoj/problem_show.php?pid=17668

题目大意：

给定一个数，按要求输出元素最少的序列。其中ak = ai + aj ( $0 \le i, j \le k-1$ ) 。

解题思路：

迭代加深搜索：

限定搜索的深度k，然后开始进行DFS搜索，如果搜索完没有解，深度k = k + 1，继续上诉搜索，直到找到可行解。

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<ctype.h>
#include<algorithm>
#include<string>
#define PI acos(-1.0)
#define maxn 1000
#define INF 1<<25
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
using namespace std;
int a[20], n, b[20], depth;
bool flag;
void dfs(int t)
{
    int i, j;
    if (flag) return ;
    if (t == depth)
    {
        if (a[t] == n) flag = true;
        return ;
    }
    for (i = 0; i <= t; i ++)
        for (j = i; j <= t; j++) if (a[i] + a[j] > a[t] && a[i] + a[j] <= n)
        {
            int sum = a[i] + a[j];
            for (int k = t + 1; k < depth; k++) sum *= 2; // 剪枝
            if (sum < n) continue;
            a[t + 1] = a[i] + a[j];
            dfs(t + 1);
            if (flag) return ;
        }
}
int main ()
{
    a[0] = 1, a[1] = 2;
    while(scanf("%d", &n) != EOF)
    {
        if (!n) break;
        int m = 1;
        depth = 0;
        while(m < n)
        {
            depth++;
            m *= 2;
        }
        flag = false;
        while(1)
        {
            dfs(0);
            if (flag) break;
            depth++;
        }
        for (int i = 0; i < depth; i++) printf("%d ", a[i]);
        printf("%d\n", a[depth]);
    }
    return 0;
}