3134.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3134  User Id:fzk 
Memory:40K  Time:921MS
Language:G++  Result:Accepted

Source 

#include <stdio.h>

using namespace std;

bool sign[1010];
int a[20];
int ans, best;

int search( int k, int big ) {
	int b = 1000, t, temp, sb;
	
	if( a[k] == ans ) {
		best = k;
		return 0;
	}

	if( k >= best )
		return 1000;
	
	int i;
	for( i=k, sb=big; sb<ans; sb<<=1, i++ )
		;
	if( i >= best )
		return 1000;

	for( int i=k; i>=k && i>=0; i-- )
	for( int j=i; j>=0; j-- ) {
		if( a[i]+a[j] <= ans && !sign[ a[i]+a[j] ] ) {
			a[k+1] = a[i]+a[j];
		
			sign[ a[k+1] ] = true;
			
			sb = big;
			if( sb < a[k+1] )
				sb = a[k+1];
				
			t = search( k+1, sb );
			if( t < b ) b = t;
			sign[ a[k+1] ] = false;
		}
	}
	
	for( int i=k; i>=k && i>=0; i-- )
	for( int j=i-1; j>=0; j-- ) {
		if( a[i] > a[j] )
			temp = a[i]-a[j];
		else
			temp = a[j]-a[i];
		
		if( !sign[ temp ] ) {
			a[k+1] = temp;
			
			sb = big;
			if( sb < a[k+1] )
				sb = a[k+1];
				
			sign[ temp ] = true;
			t = search( k+1, sb );
			if( t < b ) b = t;
			sign[ temp ] = false;
		}
	}
	return b+1;
}

int main( ) {
	int n, i;

	while( scanf( "%d", &n ) == 1 && n ) {

		for( i=0; i<=n; i++ )
			sign[i] = false;
		ans = n;
		best = 13;
		a[0] = 1;
		search( 0, 1 );
		printf( "%d\n", best );
	}
	return 0;
}