题意:给定n个长度不定的火柴,现在问能否通过这些火柴组成一个正方形;
解析:DFS搜索+剪枝;
搜索过程中,当搜到某一满足要求的火柴时,判断是否为第4根长度为某一值;如果是,则搜索完成;否则,将单次搜索单边完成,将临时记录单边长度的sum归0。
剪枝:
一、当火柴总和不能被4整除时,一定不能组成正方形,因此直接输出“no”;
二、当火柴中长度最长的一根火柴大于单边长度时,一定不能组成正方形,直接输出“no”;
三、当在搜索过程中,如果任意长度火柴的组成大于单边长度时,直接跳过搜索,会到上一起点进行搜索;
// 1.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include<cstring> #include<string> #include<cstdio> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1005; int num[ maxn ], vis[ maxn ], n, ave; bool flag; int cmp( int a, int b ){ return a < b; } void Dfs( int sum, int cur, int step ){ if( sum == ave ){ step++; cur = 0; if( step == 4 ){ flag = true; } else{ sum = 0; } } if( flag ){ return; } for( int i = cur; i < n; ++i ){ if( !vis[ i ] ){ if( sum + num[ i ] > ave ) continue; vis[ i ] = 1; Dfs( sum + num[ i ], i, step ); vis[ i ] = 0; } } } int main(){ int Case, ans; cin >> Case; while( Case-- ){ cin >> n; memset( vis, 0, sizeof( vis ) ); ans = 0; flag = false; for( int i = 0; i < n; ++i ){ cin >> num[ i ]; ans += num[ i ]; } sort( num, num + n, cmp ); ave = ans / 4; if( ans % 4 || num[ n - 1 ] > ave ){ puts( "no" ); continue; } Dfs( 0, 0, 0 ); if( flag ){ puts( "yes" ); } else{ puts( "no" ); } } return 0; }
原文:http://blog.csdn.net/bo_jwolf/article/details/19842853