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

真心不明白为什么tle,有高手帮我看一下吗?

Posted by yangzefeng at 2012-09-25 20:44:05 on Problem 2362
#include<iostream>
#include<algorithm>
using namespace std;

int sticks[25], mark[25], side, M;
bool ok;

int comp(int a, int b)
{
	return a > b;
}

void dfs(int cur, int left, int sideNum)
{
	int i;
	if(sideNum == 4)
	{
		ok = true;
		return;
	}
	for(i = cur; i < M; i++)
	{
		if(mark[i] == 1)
			continue;
		if(i > 0)
		{
			if(sticks[i] == sticks[i-1] && mark[i-1] == 0)
				continue;
		}
		if(left < sticks[i])
			continue;

		mark[i] = 1;
		if(sticks[i] == left)
		{
			int temp;
			for(temp = 0; mark[temp] == 1; temp++);
			dfs(temp, side, sideNum+1);
		}
		else
			dfs(cur+1, left-sticks[i], sideNum);
		if(ok) 
			return;
		mark[i] = 0;
		if(left == sticks[i] || left == side)
			return;
	}
	return;
}

int main()
{
	int N, sum;
	scanf("%d", &N);
	while(N--)
	{
		scanf("%d", &M);
		//init
		sum = 0;
		ok = false;
		memset(mark, 0, sizeof(mark));

		for(int i = 0; i < M; i++)
		{
			scanf("%d", &sticks[i]);
			sum += sticks[i];
		}
		//枝剪1
		if(sum % 4 != 0)
		{
			printf("no\n");
			continue;
		}
		side = sum / 4;
		
		//先进行排序再深搜
		sort(sticks, sticks+M, comp);

		//枝剪2
		if(sticks[0] > side)
		{
			printf("no\n");
			continue;
		}
		dfs(0, side, 0);

		if(ok)
			printf("yes\n");
		else
			printf("no\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