满足如下条件的序列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时，表示输入结束。

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

每个输出占一行。

 

深度优先搜索（dfs）每次选取一个分支， 不断深入， 直到到达递归边界才回溯， 但这种策略有一定的缺陷， 假如搜索树每个节点的分支数目从非常多， 并且问题的答案在某个较浅的节点上。如果一开始就选错了分支， 就很可能在不包含答案的深层子树上浪费许多时间；所以限制每次限制搜索的深度d， 多次搜索， 这和重复搜索与深层子树的规模来比， 实在是小巫见大巫了；

这道题可以看出， m的规模不会太大（<=10），所以我们用迭代加深的搜索方式， 从1开始限制深度， 若搜索失败就增加深度限制重新搜索， 直到找到一组解为止；

  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  5. typedef long long ll;
  6. const int INF = 0x3f3f3f3f;
  7. const int MAXN = 2e6 + 100;
  8. const int MAXM = 3e3 + 10;
  10. template < typename T > inline void read(T &x) {
  11.     x = 0; T ff = 1, ch = getchar();
  12.     while(!isdigit(ch)) {
  13.         if(ch == '-') ff = -1;
  14.         ch = getchar();
  15.     }
  16.     while(isdigit(ch)) {
  17.         x = (x << 1) + (x << 3) + (ch ^ 48);
  18.         ch = getchar();
  19.     }
  20.     x *= ff;
  21. }
  23. template < typename T > inline void write(T x) {
  24.     if(x < 0) putchar('-'), x = -x;
  25.     if(x > 9) write(x / 10);
  26.     putchar(x % 10 + '0');
  27. }
  29. int n, a[MAXN];
  30. bool vis[MAXN];
  32. int dfs(int now, int deep, int val) {
  33.     if(a[now] == n) return now;
  34.     if(now > deep) return 0;
  35.     for(int i = now; i >= 1; --i) {
  36.         for(int j = i; j >= 1; --j) {
  37.             if(!vis[a[i] + a[j]] && a[i] + a[j] > val && a[i] + a[j] <= n) {
  38.                 vis[a[i] + a[j]] = true;
  39.                 a[now + 1] = a[i] + a[j];
  40.                 
  41.                 int flag = dfs(now + 1, deep, a[now + 1]);
  42.                 if(flag) return flag;
  43.                 
  44.                 vis[a[i] + a[j]] = false;
  45.                 a[now + 1] = 0;
  46.             }
  47.             else if(a[i] + a[j] <= val) break;
  48.         }
  49.     }
  50.     return 0;
  51. }
  53. int main() {
  54.     while(scanf("%d", &n) && n) {
  55.         if(n == 1) {
  56.             puts("1");
  57.             continue;
  58.         } 
  59.         for(int i = 2; i <= 10; ++i) {
  60.             memset(a, 0, sizeof(a));
  61.             memset(vis, false, sizeof(vis));
  62.             a[1] = 1;
  63.             a[2] = 2;
  64.             int top = dfs(2, i, 0);
  65.             if(top) {
  66.                 for(int i = 1; i <= top; ++i) {
  67.                     write(a[i]);
  68.                     putchar(' ');
  69.                 }
  70.                 puts("");
  71.                 break;
  72.             } 
  73.         }
  74.     }
  75.     return 0;
  76. }

 

版权声明：本文为AK-ls原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/AK-ls/p/11275849.html