题解 UVA529 【Addition Chains】

· · 题解

大爆搜+剪枝

这题与NOI1999 生日蛋糕思路差不多，总的思路就是大爆搜，看似是不可能过的，但事实上又能过，太玄学了

相信看到这题都能想到思路是搜索，因为n的范围很小(n<=10000),所以我们的一个思路是枚举每一个数字，直到找到答案为止。

下面来说一说各种剪枝以及优化

round 1

这题搜索思路多样，个人认为dfs好想也好写。因为保证对每个n都有解，所以朴素的dfs是能没有问题的，不过在统计数字的个数时需要特意去操作。而iddfs则可以在搜索的过程中限定出数字的个数，且不会对时间复杂度造成影响，比较推荐。反正都是O(玄学)，有什么关系

round 2

首先是枚举顺序的的问题，楼上的部分题解建议从大到小枚举，因为最先枚举的数字越大越容易快速接近答案。但是我实测从大到小、从小到大两种枚举方法，差别不大，甚至从小到大枚举会更快一些。

round 3

可行性剪，枝因为题目要求序列是递增的，所以我们枚举到某一层时，如果这一层的数字比上一层的小，cut

round 4

可行性剪枝，序列递增，当枚举到某一层时，如果接下来的每一层都比上一层的数字大1，最后都比n大，cut

round 5

可行性剪枝，我们知道，如果一个大的数由两个比它小的数相加得到，那么这个大的数不会大于较小的两个数中较大的那个数的二倍。由这个性质我们可以推得：当枚举到某一层时，如果接下来的每一层的数字都是上一层的数字的二倍，最后都比n小，cut

round 6

以上的剪枝以及优化足以过掉该题的数据了，其实是我想不出来更好的剪枝了

以下是代码

#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
int n,d,ans[30];
void print(){
    for(int i=0;i<d;++i) printf("%d ",ans[i]);
    printf("%d\n",ans[d]);
}

bool iddfs(int deep){
    if(deep==d){
        if(ans[d]==n) return true;
        return false;
    }
    if(ans[deep]<=ans[deep-1]) return false;   //剪枝3
    if(ans[deep]+d-deep>n) return false;     //剪枝4
    if(ans[deep]*(1<<(d-deep)) <n) return false;   //剪枝5
    for(int i=0;i<=deep;++i){
        for(int j=i;j<=deep;++j){
            ans[deep+1]=ans[i]+ans[j];
            if(iddfs(deep+1))return true;
        }
    }
    return false;
}
int main(){
    ans[0] = 1;
    while(scanf("%d",&n)&&n){
        for(d=0;true;++d){
            if(iddfs(0)) break;
        }
        print();
    }
    return 0;
}

完结，撒花！