【HDU-1518】解题报告（DFS，极易TLE，剪枝）

原始题目

Square

  • Time Limit: 10000/5000 MS (Java/Others)

  • Memory Limit: 65536/32768 K (Java/Others)

  • Total Submission(s): 17274

  • Accepted Submission(s): 5409

Problem Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The first line of input contains N, the number of test cases. Each test case begins with an integer 4 ≤ M ≤ 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

Sample Input

3 
4 1 1 1 1 
5 10 20 30 40 50 
8 1 7 2 6 4 4 3 5

Sample Output

yes 
no 
yes

Source

University of Waterloo Local Contest 2002.09.21

Recommend

LL

题目大意

给定M个小木棍的长度，问能否组成一个正方形。

解题思路

题目很简单啊，思路也很简单啊，但是写出来就TLE了啊。。。如此可见dfs剪枝是多么的重要。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <queue>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
//dfs
const int maxn=25;
int stick[maxn]; 
bool vis[maxn];
int M,T,sum,len,flag,mmax,mmin; 
bool cmp(int a, int b)
{
	return a>b?1:0;
}
void dfs(int count,int now,int index)
{
	if(flag) return;
	if(count==4)
	{
		flag=1;
		return;
	}
	if(now==0)
	{
		dfs(count+1,len,M-1);
		if(flag)
			return;
	}
	else if(now<mmin) return;
	for(int i=index;i>=0;i--) //剪枝1：从index开始遍历 
	{
		if(!vis[i]&&now>=stick[i])
		{
			vis[i]=1;
			dfs(count,now-stick[i],i-1);	//i已经使用过 
			if(flag) return;
			vis[i]=0;
			if(index==M-1)<span class="space" style="white-space:pre;display:inline-block;text-indent:2em;line-height:inherit;">//剪枝2（重要剪枝）：由于每一边长度都相等，一边不能利用最长木棍的话，那么肯定这组数据肯定过不了，不需要检测了。</span>
			{
				return;
			}
		//相同的忽略 
			while(stick[i]==stick[i-1])<span class="space" style="white-space:pre;display:inline-block;text-indent:2em;line-height:inherit;"> //剪枝3：同样长度的都过不了，无需再走一遍</span>
			{
//				printf("!1");
				i--;
			}
		}
	}
	return ;
}
int main()
{
//	freopen("in.txt","r",stdin);
	scanf("%d",&T); 
	
		while(T--)
		{
			memset(vis,0,sizeof(vis));
			scanf("%d",&M);
			flag=sum=0;
			for(int i=0;i<M;i++)
			{
				scanf("%d",&stick[i]);
				sum+=stick[i];
			}
			sort(stick,stick+M);
			mmax=stick[M-1],mmin=stick[0];
			len=sum/4;
			if(sum%4||mmax>len) printf("no\n");
			else
			{
				dfs(0,len,M-1);
				if(flag) printf("yes\n");
				else printf("no\n");
			}
			
		}
		return 0;
 }

收获与反思

跟TLE斗智斗勇了一下午，慢慢嚼代码，想剪枝，确定剪枝的效果。 （等待补图）