529 - Addition Chains

[Experimenter]

Thank you

I'll try this as soon as I'll have recuperated from SWERC (it was today, and I'm a bit dead)...

Thank you

I would recommend reading this http://online-judge.uva.es/board/viewto ... 7371#47371
this is far more understandable then all IDA thing in vague terms.

[chetan]

hello everyone . i have tried to solve this problem using dfs method. but it becomes extremely slow after input is >= 25. how do i make it faster. can u give me hints......

Code: Select all

# include <iostream>
# include <vector>

using namespace std;
int a[10000],p[10000],n,m=99999999;

void dfs(int sum,int s)
{
	if(sum==n)
	{
		if(s<m){
			m=s;
			for(int j=0;j<s;j++)	p[j]=a[j];
		}
	return;
	}
	
	for(int i=s-1;i>=0;i--)
	{
		if((sum+a[i])<=n){
			a[s]=sum+a[i];
					dfs(sum+a[i],s+1);
		}
	}

}


int main()
{
	int i;
	
	while(cin>>n)
	{
	
		m=99999999;
	a[0]=1;
	
	dfs(1,1);
	
	for(i=0;i<m;i++)
		cout<<p[i]<<' ';
	
	cout<<'\n';
	}
	
	
	return 0;
}
	

[Jan]

You can use IDA* search.