hdu 1518(dfs)

题目链接 ：http://acm.hdu.edu.cn/showproblem.php?pid=1518

 

Square

 

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

 

 

 

 

题意 ：给你n条边，让你用这些边组成正方形（不多不少仅n条）。

 

分析 ：主要是超时问题，注意优化。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[22],vis[22];
int n,m,length;               //length表示要组成的正方形的边长
int ans,flag;

void dfs(int cnt,int sum, int k)   //cnt记录边数，sum记录当前边长，k记录位置
{
    if (cnt == 3)               //如果有三条边满足要求，那么第四条边一定满足要求
    {
        flag = 1;
        return ;
    }
    if (sum == length)        //找到满足要求的边，边数加一，初始化
    {
        cnt++;
        k = 0;
        sum = 0;
    }
    for (int i=k; i<m; i++)
    {
        if (!vis[i] && sum + a[i] <= length)
        {
            vis[i] = 1;
            dfs(cnt, sum+a[i], i+1);
            if (flag)         //优化时间，（当找到所有边之后就一直返回，不需要再把之后的代码运行一遍）
            {
                return ;
            }
            vis[i] = 0;
        }
    }
}

int main ()
{
    scanf ("%d",&n);
    while (n--)
    {
        ans = 0;
        scanf ("%d",&m);
        for (int i=0; i<m; i++)
        {
            scanf ("%d",&a[i]);
            ans += a[i];
        }
        if (ans % 4)              //如果所有边长和不是4的倍数，怎样都不能组成正方形
        {
            printf ("no
");
            continue ;
        }
        memset(vis, 0, sizeof(vis));
        flag = 0;
        length = ans / 4;     //记录正方形边长
        dfs(0, 0, 0);
        if (flag)
            printf ("yes
");
        else
            printf ("no
");
    }
    return 0;
}