题解 UVA529 【Addition Chains】

Naruto_steven · 2019-02-18 11:32:10 · 题解

此题是搜索，深搜+剪枝

二话不说，先上代码：

#include<bits/stdc++.h>//万能头文件 
using namespace std;
int n,ans[100];
bool finish;//记录状态
void dfs(int x,int deep){
    if(finish) return ;
    if(x==deep) { if(ans[x]==n)finish=1; return; }
    for(int i=0;i<=x;i++){
        for(int j=i;j<=x;j++) if(ans[i]+ans[j]>ans[x]&&ans[i]+ans[j]<=n){//剪枝 
                int sum=ans[i]+ans[j];
                for(int k=x+2;k<=deep;k++) sum<<=1;//sum *= 2;当前为x; sum存于x+1; 
                if(sum<n) continue;//如果接下来一直是最大策略还是不能达到n，剪枝 
                ans[x+1]=ans[i]+ans[j];
                dfs(x+1,deep);
                if(finish) return ;
        }
    }
}
int main(){
    while(scanf("%d",&n),n){
        memset(ans,0,sizeof(ans));
        ans[finish=0]=1;//直接在此初始化
        int tmp=n,deep=0; 
        while(tmp>>=1) deep++;//求出最大深度； 
        while(!finish) dfs(0,deep++);
        cout<<ans[0];
        for(int i=1;i<deep;i++) cout<<" "<<ans[i];
        cout<<endl; 
    }
    return 0;
}

然后开始讲解思路：

如果我们的答案数组ans和传参的x即ans[x]==n且x已经达到最大深度,任务结束，将finish修改为1

几个剪枝点:
1、如果枚举时ans[i]+ans[j]（随意两个数）和大于ans[x]，我们才继续；
2、还要满足ans[i]+ans[j]<=n,如果都大于n了，就不需搜索了。
3、由于我们一直按照最大策略枚举，如果还未能达到n，可以剪枝了。

牵扯到一点位运算，因为比较快，即>>和<<;

坑点：

最后不能留空格，所以

cout<<ans[0];
for(int i=1;i<deep;i++) cout<<" "<<ans[i];

输出操作要稍微修改一下