Square

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

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

题意：给一列数，问能否把这列数分成四组，且每组数的和相同。

解法：有DFS进行回溯。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int a[], n, ans;

bool vis[];

int dfs(int cur, int len, int pos)//cur表示用过的个数， len表示长度， pos表示位置

{

    if(cur==n)

    return ;

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

    {

        if(vis[i]) continue;

        if(len+a[i]<ans)

        {

            vis[i] = ;

            if(dfs(cur+, len+a[i], i+)) return ;

            vis[i] = ;

            if(len==) return ;

            while(a[i]==a[i+]&&i+<n) ++i;//剪枝

        }

        else if(len+a[i]==ans)

        {

            vis[i] = ;

            if(dfs(cur+, , )) return ;

            vis[i] = ;

            return ;

        }

    }

    return ;

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int Sum = ;

        scanf("%d", &n);

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

        {

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

            Sum+=a[i];

        }

        if(Sum%)

        {

            printf("no\n");

            continue;

        }

        ans = Sum/;

        memset(vis, , sizeof(vis));

        int temp = dfs(, , );

        printf("%s\n", temp?"yes":"no");

    }

    return ;

}

巴特西

HDU1518 Square（DFS）

Square

最新文章

热门文章