UVa 10364 : Square

UVa 演習 2014/6/9 (月) 問2

問題リンク：http://uva.onlinejudge.org/external/103/10364.html

問題概要：
最大２０本の棒があり、それらの長さが与えられる
これを使って正方形をつくれるか？

解法：
再帰で探索する
POJのsticksの下位互換

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

const string YES = "yes", NO = "no";

int M,L;
int sticks[21];

bool dfs(int bitmask,int len,int sp){

  if( bitmask == ((1<<M)-1) ) {
    return len == 0;
  }

  REP(i,sp,M){
    if( (bitmask>>i) & 1 ) continue;
    int nlen = len + sticks[i];
    if( nlen > L ) {
      continue;
    } else if( nlen == L ) {
      return dfs(bitmask|(1<<i),0,0);
    } else {
      if( dfs(bitmask|(1<<i),nlen,i+1) ) return true;
    }
  }
  return false;
}

int main(){
  int N;
  cin >> N;
  while( N-- ){
    cin >> M;
    int sum = 0;
    rep(i,M) {
      cin >> sticks[i];
      sum += sticks[i];
    }

    if( sum % 4 ) {
      cout << NO << endl;
      continue;
    }

    sort(sticks,sticks+M);

    L = sum / 4;
    cout << (dfs(0,0,0)?YES:NO) << endl;

  }
  return 0;
}