Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

暴搜 g++ 141ms

Posted by Idy002 at 2014-08-19 20:01:13 on Problem 1950
#include <cstdio>
#include <cstring>
#define Abs(a) ((a)<0?-(a):(a))

int n;
char path[16];
char fpath[21][16]; int tot;
/*
last 上一个加减号后的值(连起来的也算)
*/
int dfs( int i, int last, int sum ) {
	if( i==n+1 ) {
		if( sum==0 ) {
			if( tot<20 ) {
				tot++;
				memcpy( fpath[tot], path, sizeof(path) );
			}
			return 1;
		}
		return 0;
	}
	int r=0;
	path[i] = '+';
	r += dfs( i+1, +i, sum+i );
	path[i] = '-';
	r += dfs( i+1, -i, sum-i );
	if( Abs(last)>=123456789 ) return r;
	path[i] = '.';
	int now=last*(i>=10?100:10)+i*(last<0?-1:1);
	r += dfs( i+1, now, sum-last+now );
	return r;
}
int main() {
	int r;
	scanf( "%d", &n );
	r = dfs( 2, 1, 1 );
	for( int t=1; t<=tot; t++ ) {
		printf( "1" );
		for( int i=2; i<=n; i++ ) 
			printf( " %c %d", fpath[t][i], i );
		printf( "\n" );
	}
	printf( "%d\n", r );
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator