2068885 2006-09-15 22:28:27 Accepted 1937 C++ 00:00.02 436K St.Crux     给定队列首数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);  } }}

评论