题解 UVA529 【Addition Chains】

珈乐唯毒 · 2020-04-30 11:01:12 · 题解

代码思路：

本题我们不知道m是多少，甚至连m的上限也不清楚。

对于枚举次数不明确的题目，我们可以使用迭代加深搜索(IDA)的思路。对这道题目而言，我们可以先从m=2开始尝试(前提是n!=1)，如果m=2不行，再尝试m=3，这样一步步增加m。

上AC代码

#include<bits/stdc++.h>
using namespace std;
int n,a[10000005],m;
bool dfs(int x){
    if(x==m){
        if(a[x]==n){
            for(int i=1;i<m;i++)printf("%d ",a[i]);
            printf("%d",a[m]);
            return true;
        }
        return false;
    }
    for(int i=1;i<=x;i++){
        for(int j=i;j<=x;j++){
            a[x+1]=a[i]+a[j];
            if(dfs(x+1))return true;
        }
    }
    return false;
}
int main(){
    cin>>n;
    while(n!=0){
        a[1]=1;
        if(n==1)printf("1");
        for(m=2;m<=n;m++)if(dfs(1))break;
        cin>>n;
        if(n!=0)printf("\n");
    }
    return 0;
} 

然后你就爆了（毕竟AC被划掉了呢）

本道题的n会到10000，这样写是肯定会爆的了。

因此考虑剪枝

剪枝1： 我们可以从大到小来枚举a[i]+a[j]这样会快一些 剪枝2： 考虑当前值是不是过大，如果当前值每次只加一都会大于n，就return false 剪枝3： 考虑当前值是不是过小，如果当前值每次乘二都会小于n，就return false 剪枝4： 如果已经有了答案，就return true

上真正的AC代码

#include<bits/stdc++.h>
using namespace std;
long long n,a[10000005],m;
bool p;
bool dfs(long long x){
    if(p==1)return true;//剪枝4
    if(a[x]<<(m-x)<n)return false//剪枝2;
    if(a[x]+m-x>n)return false;//剪枝1
    if(x==m){
        if(a[x]==n){
            for(int i=1;i<m;i++)printf("%d ",a[i]);
            printf("%d",a[m]);
            p=1;
            return true;
        }
        return false;
    }
    for(int i=x;i>=1;i--){
        for(int j=x;j>=i;j--){//剪枝3
            a[x+1]=a[i]+a[j];
            if(a[x+1]<=a[x])break;
            if(dfs(x+1))return true;
        }
    }
    return false;
}
int main(){
    cin>>n;
    while(n!=0){
        p=0;
        a[1]=1;
        if(n==1)printf("1");
        for(m=2;m<=n;m++)if(dfs(1))break;
        cin>>n;
        printf("\n");//注意格式，最后会多空一行，但是每一组数据最后不能多一个空格
    }
    return 0;//完结撒花
}