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

单纯DFS居然也过了

Posted by CodesW at 2016-08-14 10:58:55 on Problem 1014 and last updated at 2016-08-14 11:10:26
#include <stdio.h>

int dfs(int *n, int val, int max)
{
	int i = 0 ;

	if(0 == val)
		return 1 ;

	for(i = max; i > 0; i--)
	{
		if(!n[i-1] || val < i)
			continue ;
		
		n[i-1]-- ;
		if(dfs(n, val - i, i))
			return 1 ;
	}

	return 0 ;
}

int main(int argc, char *argv[])
{
	int  n[6] = {0} ;
	int  cnt = 0 ;
	int  i = 0 ;
	int  sum = 0 ;

	while(1)
	{
		sum = 0 ;
		for(i = 0; i < 6; i++)
		{
			scanf("%d ", &n[i]) ;
			
			/* 神奇剪枝 */
			/* n[i] %= 60 ; */

			sum += n[i] * (i+1) ;
		}
		if(0 == sum)
			break ;

		printf("Collection #%d:\r\n", ++cnt) ;

		if((sum % 2) || (0 == dfs(n, sum/2, 6)))
			printf("Can't be divided.\r\n\r\n") ;
		else
			printf("Can be divided.\r\n\r\n") ;
	}

	return 0 ;
}


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