hdu Square DFS

Square

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 5604    Accepted Submission(s): 1776

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

/* 
1优化
   如果按照素数环的方法，是暴搜的。超。
   当第一次满足if(p==sum)的时候，(1).不需要再继续搜索下去，(2).而且从头再开始搜。
   要满足(1),(2)我们在DFS中设立两个相应的变量n,p；
   if(sum=p+f[i]) dfs(0,0,cur+1);
   else if(p+f[i]<sum) dfs(i,p+f[i],cur);
   if(p==0) break;
   这样话，能有效的处理满足 cur++的情况时，退出当前的搜索。
   另外当数字相同的时候也处理，while(f[i]==f[i+1]) i++;
2优化
   如果排序，从大到小进行选择数字，避免了随机，能提高速度。
3优化
   if(sum%4!=0) no
   else sum=sum/4;
   cur只要满足 3 就可以了,不需要4。
*/
#include<stdio.h>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
int f[10003];
int visit[10003];
int flag;
int sum;
int m;
bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int n,int p,int cur)
{
    int i;
    if(cur==3)
    {
        flag=1;
        return;
    }
    if(flag==1) return;
    for(i=n+1;i<=m;i++)
    {
        if(visit[i]==0 && flag==0)
        {
            visit[i]=1;
            if(p+f[i]==sum)
                dfs(0,0,cur+1);
            else if(p+f[i]<sum)
                dfs(i,p+f[i],cur);
            visit[i]=0;
            if(p==0) break;
            while(f[i]==f[i+1]) i++;
        }
    }
}
int main()
{
    int i,j,n;
    while(scanf("%d",&n)>0)
    {
        while(n--)
        {
            scanf("%d",&m);
            sum=0;
            for(i=1;i<=m;i++)
            {
                scanf("%d",&f[i]);
                sum=sum+f[i];
            }
            if(sum%4!=0)
            {
                printf("no
");
                continue;
            }
            sort(f+1,f+1+m,cmp);
            for(j=0;j<=m;j++)
                visit[j]=0;
            flag=0;sum=sum/4;
            dfs(0,0,0);
            if(flag==1) printf("yes
");
            else printf("no
");
        }
    }
    return 0;
}