一本通【例题4】Addition Chains—

一本通【例题4】Addition Chains——题解

又是一道剪枝剪了半天的搜索题。。。题目传送

要充分利用题目中的约束条件：1、；2、对于每个 $k (1 \leq k \leq m)$

还是先找找搜索过程要面临的状态和有关维度：目标数n,答案序列的长度limit，序列中的每个数ai，当前序列中的最后一个数last。

由于如果不对序列长度加以限制，普通的深搜便会“一发不可收拾”，所以这里用迭代加深搜索。

可行性剪枝考虑：

　　　1、由于迭代加深搜索会把之前的状态全搜索一遍，所以应当限制一下limit的下界。注意到长度为k的序列能最大造出来的数为2^k-1，所以序列最短应保证那个最大造出来的数>=n，预处理就行。

考虑一下搜索顺序：因为n是由小数加小数构造出来的，求最小的构造次数。因此应从大到小搜索。

考虑防等效冗杂：让从大到小枚举的两个数中的第1个正常枚举、第2个从第1个开始枚举。

继续考虑可行性剪枝：

　　　2、当前枚举的序列里的两个数相加应大于last，只有这样才能继续搜索。

　　　3（效率还不够，更近一步考虑一下未来）：发现一个序列最大的增长方式即为让序列中最后一个数自己加自己，设这个数为a，进行k次这样的增长后序列中最后的一个数则为a*2^k，每次增长操作都会增加一个数。对于当前长度为l的序列，如果last*2^limit-l仍小于n，就回溯；等于n，那limit一定是答案；大于n时才继续搜索。2的幂次方可打表或预处理出。

最优性剪枝：找到答案就停止就行。

AC代码：

  1 #include<iostream>
  2 #include<cstdio>
  3 
  4 using namespace std;
  5 
  6 int n,a[10000],bj,cankao[1055],mi[20];
  7 
  8 void dfs(const int &limit,int k)//要填第k个(k从1开始） 
  9 {
 10     if(bj) return;
 11     if(k==limit)
 12     {
 13         for(int i=k-2;i>=0;i--)
 14             for(int j=i;j>=0;j--)
 15             {
 16                 if(a[i]+a[j]==n)
 17                 {
 18                     a[k-1]=n;
 19                     bj=1;
 20                     return;
 21                 }
 22             }
 23     }
 24     if(a[k-2]*mi[limit-k+1]<=n)//可行性剪枝3 
 25     {
 26         if(a[k-2]*mi[limit-k+1]==n) 
 27         {
 28             bj=1; 
 29             for(int j=k-1;j<limit;j++)
 30             a[j]=a[j-1]*2;
 31         }
 32         return;
 33     }
 34     for(int i=k-2;i>=0;i--)
 35     {
 36       for(int j=i;j>=0;j--)//防等效冗杂 
 37         if(a[i]+a[j]>a[k-2])
 38         {
 39             if(a[i]+a[j]>=n) continue;//可行性剪枝2 
 40             a[k-1]=a[i]+a[j];
 41             dfs(limit,k+1);
 42             if(bj) return;
 43         }
 44         else
 45         {
 46             if(j==i) return;
 47             break;
 48         }
 49     }    
 50 } 
 51 
 52 void work()
 53 {
 54     bj=0;
 55     for(int len=cankao[n];len<=n;len++)
 56     {
 57         dfs(len,3);
 58         if(bj) 
 59         {
 60             for(int i=0;i<len;i++)
 61                 printf("%d ",a[i]);
 62             putchar('
');
 63             return;
 64         }
 65     }
 66 }
 67 
 68 void init()
 69 {
 70     int i=1,step=1;
 71     while(i<=1024)
 72     {
 73         cankao[i]=step;
 74         i*=2;
 75         step++;
 76     }
 77     for(i=1;i<=1000;i++)
 78         if(!cankao[i])
 79             cankao[i]=cankao[i-1];//以上为可行性剪枝1 
 80     i=1,step=1;
 81     mi[1]=1;
 82     for(int j=1;j<=20;j++)//2的幂次方的预处理 
 83     {
 84         i*=2;
 85         mi[j]=i;
 86     }
 87 }
 88 
 89 int main()//预处理 
 90 {
 91     init();
 92     a[0]=1;a[1]=2;//注意序列下标0开始 
 93     scanf("%d",&n);
 94     while(n)
 95     {
 96         if(n==1)//处理特殊情况 
 97         {
 98             putchar('1');
 99             putchar('
');
100         }
101         if(n==2)
102             cout<<"1 2
";
103         if(n>=3)
104         work();
105         scanf("%d",&n);
106     }
107     return 0;
108 }