给定队列首数1和尾数N，求一个最短升序队列，之中每一个数都可以用队列中其余两个数（可以相等）之和表示。

    这题相当的棒。似乎是枚举构造orz，然而可以用搜索dfs，搜到（加到）N时停止并判断长度。但如果用一个二重循环不断搜索，下场就是死。所以还需要优化。

    首先需要计算出，对于队列的最后第二个数M，累计到N最小需要多少步。因为2M到M需要一步，所以s[M] = s[M + M] + 1。这是题目的关键。比如49到98是一步，到100就至少要两步。

    然后剪枝：如果s[M] + 目前的长度已经不可能再得到最优解时停止。这种剪枝非常常见。我一开始没有考虑SM的情况，结果很惨。

#include <cstdio>

int n, ans, a[100], r[100], d[202];

void dfs(int);
void print();
void init();

int main()
{
 //freopen("in.txt", "r", stdin);
 while(scanf("%d", &n) && n)
 {
  init();
  dfs(0);
  print();
 }
 return 0;
}

void init()
{
 int i;
 ans = n;
 a[0] = 1; 
 for(i = n; i <= n + n; i ++) d[i] = 0;
 for(i = n - 1; i > 0; i --)  d[i] = d[i + i] + 1;
}

void print()
{
 int i;
 for(i = 0; i < ans; i ++)
 {
  printf("%d ", r[i]);
 }
 printf("%d\n", n);
}

void dfs(int l)
{
 int i, k; 
 if(l + d[a[l]] >= ans)
  return;  //prunation
 if(a[l] == n)
 {
  ans = l;
  for(i = 0; i < l; i ++)
  {
   r[i] = a[i];
  }
  return;
 }
 for(i = l; i >= 0; i --)
 {
  for(k = i; k >= 0; k --)
  {
   a[l + 1] = a[i] + a[k];
   if(a[l + 1] > a[l] && a[l + 1] <= n)
    dfs(l + 1);
  }
 }
}

评论