杭电1518题（深搜）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1518
代码如下：

#include<bits/stdc++.h>
using namespace std;
bool flag;  //是否可以成功 
int n,sums;   //木棍数量，木棍长度总和 
int stick[25];   //木棍长度数组 
bool vis[25];    //访问数组 
void dfs(int p,int ans,int t)  
{   //p已经组合好的正方形边，ans当前长度和，t当前木棍数组下标 
	if(ans==sums/4)  //如果长度达到了 
	{
		p++;  //边数加一 
		if(p==4)  //凑成了正方形 
		{
			flag=true; 
			return;
		}
		else ans=0;  //否则长度清零 
		t=0;
	}
	if(flag)  return;
	for(int i=t;i<n;i++)  //遍历每个木棍 
	{
		if(!vis[i]&&ans+stick[i]<=sums/4)  //没有访问过，并且长度小于等于正方形边长 
		{
			vis[i]=true;  //标记访问过 
			dfs(p,ans+stick[i],i);
			vis[i]=false; //回溯 
		}
	}
}
int main()  
{  
	int t,maxn;
	cin>>t;
	while(t--)
	{
	    cin>>n;
	    sums=0;  maxn=-1;
		for(int i=0;i<n;i++)
		{
		    cin>>stick[i];
			if(maxn<stick[i])  maxn=stick[i];
			sums+=stick[i];	
	    }
		if(sums%4!=0||maxn>sums/4)	cout<<"no"<<endl; //如果长度不能平分为四条边或者某边过大 
		else
		{
			flag=false;
			dfs(0,0,0);
			if(flag) cout<<"yes"<<endl;
			else cout<<"no"<<endl;
		}
	}
	return 0;  
}  

最后

以上就是深情鸭子为你收集整理的杭电1518题（深搜）的全部内容，希望文章能够帮你解决杭电1518题（深搜）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。