[UVa] 10364 - Square

題意:
(from luckycat)


解法:
用 DFS 枚舉所有的可能再搭配剪枝，剪掉不可能的情況。
參考 http://blog.csdn.net/kkkwjx/article/details/18308373。

注意:

程式碼:

	/**
	* Tittle: 10364 - Square
	* Author: Cheng-Shih, Wong
	* Date: 2015/07/10
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 25
	typedef vector< int > VI;
	// declarations
	int n, t;
	bool used[N];
	int sum, tLen;
	VI sticks;
	// functions
	bool cmp( int a, int b )
	{
	return a > b;
	}
	void init()
	{
	int val;
	clr( used, false );
	sticks.clear();
	cin >> n;
	sum = 0;
	FOR( i, 1, n ) {
	cin >> val;
	sum += val;
	sticks.push_back(val);
	}
	sort( sticks.begin(), sticks.end(), cmp );
	tLen = sum/4;
	}
	bool dfs( int sum, int layer, int idx )
	{
	if( layer==3 ) return true;
	FOR( i, idx, sticks.size()-1 ) if( !used[i] ) {
	if( i>0 && !used[i-1] && sticks[i]==sticks[i-1] ) continue;
	if( sum+sticks[i] > tLen ) continue;
	used[i] = true;
	if( sum+sticks[i]==tLen ) {
	if( dfs( 0, layer+1, 0 ) ) return true;
	} else {
	if( dfs( sum+sticks[i], layer, i+1 ) ) return true;
	}
	used[i] = false;
	if( sum==0 ) return false;
	}
	return false;
	}
	bool check()
	{
	if( sum%4 != 0 ) return false;
	for( int len:sticks )
	if( len > tLen ) return false;
	return dfs( 0, 0, 0 );
	}
	// main function
	int main( void )
	{
	// input
	cin >> t;
	while( t-- ) {
	init();
	if( check() ) puts("yes");
	else puts("no");
	}
	return 0;
	}

view raw 10364 - Square.cpp hosted with ❤ by GitHub