3187.txt

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

Source

Problem Id:3187  User Id:fzk 
Memory:3124K  Time:0MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>

int n, m;
int c[11], a[11];
bool flag[10260][1024];

void clac_c( ) {
	int i, j;
	for( i=1; i<n; i++ )
		c[i] = 0;
	c[0] = 1;
	for( i=1; i<n; i++ )
		for( j=n-1; j; j-- )
			c[j] += c[j-1];
}

bool search( int sum, int k, int sign ) {
	int i;
	if( flag[sum][sign] )
		return false;

	if( sum > m )
		return false;
	
	if( k == n )
		return sum == m;

	for( i=1; i<=n; i++ )
		if( (sign & 1<<(i-1)) == 0 ) {
			a[k] = i;
			if( search( sum+c[k]*i, k+1, sign | 1<<(i-1) ) )
				return true;
		}
	flag[sum][sign] = true;
	return false;
}

int main( ) {
	scanf( "%d%d", &n, &m );
	clac_c( );
	search( 0, 0, 0 );
	for( int i=0; i<n; i++ )
		printf( "%d ", a[i] );
	printf( "\n" );
	return 0;
}