题解 UVA529 【Addition Chains】

· · 题解

迭代加深+剪枝 看完题目第一反应求最短路：bfs；看了一眼n=10000，肯定会爆空间。因此考虑dfs，按照dfs去跑会发现暴力dfs可能得不到正确答案；转念一想这不就是dfs形式的bfs吗？这不就是迭代加深？？

快速写完迭代加深后样例数据一发就过了，信心倍增；但是输入10000之后发现它好像不动了。。。。。这样一定会T;

考虑剪枝，不难看出我们需要的序列是单调递增的，枚举i,j得到k；因此如果发现ans[i]+ans[j]>n，那么如果i不变，j往后增一定也大于n；不过这并不会有什么大的改观；

强剪枝：ans[i]<=ans[i-1]2，也就是说后一项最多是前一项的2倍，如果当前已知ans[k]然后迭代加深的最大深度为maxd，则后面最多还有maxd-k项，也就是说ans[k]2^k<n则在maxd次之内一定找不到答案。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
long long n,maxd,ans[N];
bool dfs(int k){
    if(k>maxd)return ans[k-1]==n;
    if(ans[k-1]*((long long)1<<(maxd-k+1))<n)return 0;//最优化剪枝：后面每一项最多是前一项的2倍 
    for(int i=0;i<k;i++)
        for(int j=i;j<k;j++){
            long long t=ans[i]+ans[j];
            if(t>n)break;//可行性剪枝：ans单调递增，如果t>n则后面的j都会大于n； 
            if(t<=ans[k-1])continue; //保证ans单调递增 
            ans[k]=t;
            if(dfs(k+1))return 1;
        }
    return 0;
}
int main(){
    ans[0]=1;
    while(scanf("%lld",&n)&&n){
        printf("1");
        for(maxd=0;;maxd++){
            if(dfs(1)){
                for(int i=1;i<=maxd;i++)
                    printf(" %lld",ans[i]);
                printf("\n");
                break;
            }
        }
    }
    return 0;
}