ZOJ 1909 I-Square

https://vjudge.net/contest/67836#problem/I

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

代码：

#include <bits/stdc++.h>

using namespace std;

int n, ave, maxx, sum;

int a[50];

bool flag = false;

int vis[50];

void dfs(int num, int len, int start) {

    if(flag)

        return;

    if(num == 4) {

        flag = true;

        return ;

    }

    if(len == ave) {

        dfs(num + 1, 0, 1);

        if(flag)

            return ;

    }

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

        if(vis[i] == 0 && len + a[i] <= ave) {

            vis[i] = 1;

            dfs(num, len + a[i], i + 1);

            vis[i] = 0;

            if(flag)

                return ;

        }

    }

}

int main() {

    int T;

    scanf("%d", &T);

    while(T --) {

        scanf("%d", &n);

        maxx = 0, sum = 0;

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

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

            sum += a[i];

        }

        sort(a + 1, a + 1 + n);

        maxx = a[n];

        ave = sum / 4;

        if(sum % 4 != 0 || maxx > ave) {

            printf("no\n");

            continue;

        }

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

        flag = false;

        dfs(0, 0, 1);

        if(flag)

            printf("yes\n");

        else

            printf("no\n");

    }

    return 0;

}

　　写这个专题的时候想到暑假被搜索支配的恐惧写不出来或者很紧张的时候就很喜欢听《最佳歌手》

巴特西

ZOJ 1909 I-Square

最新文章

热门文章