HDU1518 DFS Square

Square

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 12231    Accepted Submission(s): 3897

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

解释都在代码里面，超时了好多次

#include <iostream>

#include <algorithm>

#include <stdio.h>

#include <string.h>

using namespace std;

int a[22];

bool vis[22];

bool flag;

int n,sum;

void DFS(int num,int l,int k)

{

    if(flag)

        return;

    if(num == 5)    ///四条边都已经找到

    {

        flag = 1;

        return;

    }

    if(l == sum)    ///找到一条边后，继续从0开始遍历

    {

        DFS(num + 1,0,0);

        if(flag)    ///减枝，节约时间

            return;

    }

    for(int i = k; i <= n; i ++)

        if(!vis[i] && a[i] + l <= sum)

        {

            vis[i] = 1;

            DFS(num,a[i] + l,i + 1);

            if(flag)    ///减枝，节约时间

                return;

            vis[i] = 0;

        }

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t --)

    {

        sum = 0;

        scanf("%d",&n);

        for(int i = 1; i <= n; i ++)

            scanf("%d",&a[i]),sum+=a[i];

        if(sum % 4 != 0)    ///不能组成正方形

        {

            printf("no\n");

            continue;

        }

        sum /= 4;   ///每条边的长度

        int i;

        for( i = 1; i <= n; i ++)   ///是否有值超过每条边的长度

            if(a[i] > sum)

                break;

        if(i != n + 1)  ///有

        {

            printf("no\n");

            continue;

        }

        flag = 0;

        memset(vis,0,sizeof(vis));

        vis[0] = 1;

        DFS(1,0,0);///第一个是边，第二个是计算的每条边的长度，最后是当前所遍历的位置

        if(flag)

            printf("yes\n");

        else

            printf("no\n");

    }

}