Addition Chains poj

1.搜索顺序：从从大到小枚举，可以实现一部分的剪枝，个人感觉就是在枚举小的时候可能会超过最优解，直接return。
2.其实每次枚举只需要一个循环，我还很sb的要两个循环，因为剩下的循环之前已经完成了，没有必要继续下去。
3.注意输入输出格式，数组不要开小。
代码如下

#include<iostream>
#include<cstdio>
using namespace std;

int ans[100000],a[100000];int m,cnt;

void dfs(int step){
    if(a[step-1]==m&&(step-1)<cnt){
    	cnt=step-1;
    	for(int i=1;i<=step-1;++i)ans[i]=a[i];
	    return;
	}
	if(step>cnt)return;
    if(a[step-1]>m)return;
    for(int i=step-1;i>=1;--i){
    	if(a[step-1]+a[i]<=m){
    		a[step]=a[i]+a[step-1];
			dfs(step+1);a[step]=0;
		}
	}
}

int main(){
	a[1]=1;cnt=99999999;
    while(scanf("%d",&m)!=EOF) {
       if(m==0)break;
        else{
            a[1]=1;  
            cnt=999999;  
            dfs(2);  
            for(int i=1;i<=cnt;i++) printf("%d ",ans[i]);  
            printf("n");
        }
        memset(ans,0,sizeof(ans));memset(a,0,sizeof(a));
    }
	return 0;
}

感想：第一点代码能力不行，找错能力不行，有思路写不出来。有大思路，小细节写不出来

最后

以上就是纯真面包为你收集整理的Addition Chains poj的全部内容，希望文章能够帮你解决Addition Chains poj所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。