首页 > 其他 > 详细

Square

时间:2014-02-25 17:34:31      阅读:281      评论:0      收藏:0      [点我收藏+]

题意:给定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;
}


Square

原文:http://blog.csdn.net/bo_jwolf/article/details/19842853

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!