洛谷 P2383 狗哥玩木棒

题目背景

狗哥又趁着语文课干些无聊的事了...

题目描述

现给出一些木棒长度，那么狗哥能否用给出的木棒（木棒全用完）组成一个正方形呢？

输入输出格式

输入格式：

输入文件中的第一行是一个整数n表示测试的组数，接下来n行表示每组的测试数据。 每行的第一个数为m(4<=m<=20),接下来m个数ai(1<=ai<=1000)表示木棒的长度。

输出格式：

对于每组测试数据，如果可以组成正方形输出“yes”，否则输出“no”。

输入输出样例

输入样例#1：

3

4 1 1 1 1

5 10 20 30 40 50

8 1 7 2 6 4 4 3 5

输出样例#1：

yes

no

yes

说明

狗哥快抓狂了

dfs

屠龙宝刀点击就送

#include <algorithm>

#include <cstring>

#include <cctype>

#include <cstdio>

using namespace std;

inline void Read(int &x)

{

    register char ch=getchar();

    for(x=;!isdigit(ch);ch=getchar());

    for(;isdigit(ch);x=x*+ch-'',ch=getchar());

}

bool flag,use[];

int n,m,a[],sum;

void dfs(int now,int num,int z)

{

    if(flag) return;

    if(num==&&z==m) {flag=;return;}

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

    {

        if(!use[i]&&now+a[i]<=sum)

        {

            use[i]=;

            (now+a[i])%sum==?dfs((now+a[i])%sum,num+,z+):dfs((now+a[i])%sum,num,z+);

            use[i]=;

        }

    }

}

int main()

{

    Read(n);

    for(;n--;)

    {

        sum=;

        flag=;

        Read(m);

        for(int i=;i<=m;++i) Read(a[i]),sum+=a[i];

        if(sum%) {printf("no\n");continue;}

        sort(a+,a++m);

        sum/=;

        dfs(,,);

        if(flag) printf("yes\n");

        else printf("no\n");

    }

    return ;

}