POJ 2362 Square

简単に枝を探して、意外にも1时间书いて、まず棒の长さと四整除されるかどうかと最も长いことを判断します
の棒が辺の長さ(和の4分の1)より大きいかどうか.棒の長さを長さから短い順に並べて、検索した辺を記録し、構成する
3つの辺は正方形を構成している.

/*Accepted    164K    235MS    C++    1396B    2012-07-27 14:30:28*/

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

using namespace std;



const int MAXN = 1 << 7;

int m, a[MAXN], sum, side, flagcnt;

bool flag, used[MAXN];



bool cmp( const int i, const int j)

{

    return i > j;

}



void init()

{

    scanf( "%d", &m);

    sum = 0;

    flag = false;

    memset( used, false, sizeof used);

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

    {

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

        sum += a[i];

    }

    side = sum / 4;

}



void dfs( int st, int now, int flagcnt)

{

    if(flagcnt == 3){

        flag = true;

        return;

    }

    if(now == side) dfs( 1, 0, flagcnt + 1);

    if(flag) return;

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

    {

        if( !used[i] && now + a[i] <= side)

        {

            used[i] = true;

            dfs( i + 1, now + a[i], flagcnt);

            if(flag) return;

            used[i] = false;

        }

    }

}





bool judge()

{

    if(a[1] > side || sum % 4 != 0)

        return false;

    return true;

}



int main()

{

    int T;

    scanf( "%d", &T);

    while( T --)

    {

        init();

        if( !judge()) {

            printf( "no
");

            continue;

        }

        sort( a + 1, a + m + 1, cmp);

        dfs(1, 0, 0);

        if( flag)

            printf( "yes
");

        else

            printf( "no
");

    }

    return 0;

}