HDOJ 1518 Square(DFS+剪枝)_想飞的小菜鸡丶的博客-程序员秘密

技术标签: ------题解------  

Square

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 13562    Accepted Submission(s): 4298


Problem Description
Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
 

Input
The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.
 

Output
For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".
 

Sample Input
  
   
3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5
 

Sample Output
  
   
yes no yes
 

Source


思路:
题意,给出这么多棍棍,问你能不能拼成正方形。想法肯定是DFS,但是如果是朴素的DFS的话,TLE。。所以这里又需要用剪枝的思想。。。
这里需要剪枝的几个地方是:
1、进行DFS搜索,要标记已经使用了的棍子,一旦不符合要求,就要回溯,并且棍子成为没有使用的状态。
2、当符合要求的棍子数等于5时,说明已经全部构成正方形的边长,结束。
3、每当边长达到要求是,进入下一根棍子DFS搜索。
4、还有最重要的一点:每次遍历一边棍子不要从0开始,从上一次搜索状态的下一根棍子开始遍历,否者会超时。
5、当flag为true,return的不仅是使flag变为true的那一次dfs,而且还要return 整个dfs,即结束全部的寻找。我就是在这里T了好长时间。。。

代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int s[25];
int book[25];
int sum;
int bianchang;
int n;
bool flag=false;
//第一次TLE了,dfs部分需剪枝 
void dfs(int num,int nowlen,int dth)
{
	if(num>4)
	{
		flag=true;
		return ;
	}
	
	if(dth>n)
	{
		return ;
	}
	
	if(nowlen==bianchang)
    {
        dfs(num+1,0,0);
        if(flag==true)return;//剪枝处1 
    }
    
    for(int i=dth;i<n;i++)
    {
    	if(book[i]==0&&s[i]+nowlen<=bianchang) 
        {
            book[i]=1;
            dfs(num,s[i]+nowlen,i+1);
            if(flag==true)return ;//剪枝处2 
            book[i]=0; 
        }
        else if(book[i]==0&&s[i]+nowlen>bianchang) return;
    }
} 

int main()
{
	freopen("in.txt","r",stdin);
	int num;
	cin>>num;
	while(num--)
	{
		int sum=0;
		scanf("%d",&n);
		for(int i=0;i<n;i++)
		{
			scanf("%d",&s[i]);
			sum+=s[i];
		}
		if(sum%4!=0)
		{
			cout<<"no"<<endl;
			continue;
		} 
		else bianchang=sum/4;
		bool flagg=true;
		for(int i=0;i<n;i++)
		{
			if(s[i]>bianchang)
			{
				flagg=false;
				break;
			}
		}
		if(flagg==false)
		{
			cout<<"no"<<endl;
			continue;
		}
		memset(book,0,sizeof(book));
		sort(s,s+n);
		flag=false; //每次记得再将flag初始化 
		dfs(1,0,0);
		if(flag==true)cout<<"yes"<<endl;
		else cout<<"no"<<endl;	
	}
	return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/hhu1506010220/article/details/52802114

智能推荐

伴工信部加快5G发展东风,车联网规模部署时代一触即发_5G行业应用的博客-程序员秘密

| 文章版权所有,未经授权请勿转载或使用2020年3月24日,工业和信息化部印发《关于推动5G加快发展的通知》,明确提出加快5G网络建设部署、丰富5G技...

vSAN Health Service-物理磁盘运行状况-物理磁盘运行状况检索问题(2149291)_z荒野求生的博客-程序员秘密_物理磁盘运行状况检索问题

vSAN Health Service-物理磁盘运行状况-物理磁盘运行状况检索问题(2149291)https://kb.vmware.com/s/article/2149291上次更新时间:2020/5/15分类:如何6语言: 简体中文)日本英语 订阅细节本文介绍了vSAN运行状况服务中的“物理磁盘运行状况–物理磁盘运行状况检索”问题检查,并提供了有关为什么可能报告错误的详细信息。...

remote: HTTP Basic: Access denied的解决方法_moguPeople的博客-程序员秘密

问题git执行 git clone 或者 git push 报以下错误: remote: HTTP Basic: Access denied fatal: Authentication failed for 'http://git.xxxx.com/xxxxx.git/'原因账号密码验证不通过,密码或者权限不对,导致 Git 操作失败。解决方法一 (最有效)输入:git config --system --unset credential.helper再次进行 Git 操作,输入正确的用户

长短租公寓管理系统_HZZD_HZZD的博客-程序员秘密

根据长短租公寓管理系统,从公寓的房源管理、房客的合同书管理、日常的智能化管理和公寓租赁的账务管理等方法,完成减少经营成本,提升公寓的经营高效率。长短租公寓管理系统解决方案1、搞好公寓的房源管理,减少房源空置率根据系统软件预置的房源模版,大批量统一编写,道别手工制作录入,提高工作效率和准确度;公寓房源能够查询空房,微信小程序端,减少出租率;而智能的房态管理能够把搬入、闲置,租期情况信息等都能够保证一目了然,能够大大减少人工成本。2、线上签订电子合同,签订更标准公寓管理系统可完成线上签订

PyQt 滚动条背景透明_柯哀的眼的博客-程序员秘密_滚动条背景色透明

self.setStyleSheet("QScrollBar {\ width: 10px;\ background: #003c3c3c;\ margin: 0px,0px,0px,0px;\ padding-top: 0px;\ .

使用esl控制freeswitch_淡定是个好东西的博客-程序员秘密_esl freeswitch

今天试了一下使用通过esl来控制freeswitch,按照《freeswitch权威指南》的19.1.1和19.1.2章节,执行make没有通过,其实刚开始也觉得挺诧异的,莫名其妙的从哪来的libesl.a,直接按照书上那样写,直接就报错了,找不到libesl.a,这就对了么,不安装esl,哪来的libesl.a啊,后来经过多方面寻找资料,终于找到了。首先需要安装esl,安装方法是 cd

随便推点

异常:java.security.InvalidAlgorithmParameterException the trustAnchors parameter must be non-empty解决方案_朱茂强的博客-程序员秘密

当你Java中有远程调用的第三方的https的接口,往生产环境发布后容易引发这个异常,通常你本地运行不会出现问题,只有线上会出现这个问题。问题出现的根本原因是:你线上的JDK通常都是OpenJDK,JRE的信任库和windows中安装的JDK中的不一样,OpenJDK中的JRE的默认信任库由于某种原因是空的(大小只有32字节,而在Windows上是80多kb)。网上有很多解决方案,比如同过修改java代码绕过ssl证书,但这样总觉得很蹩脚……...

VB.NET使用JSON.NET集合序列及反序列实例_落叶逸的博客-程序员秘密_.net json list

Imports Newtonsoft.JsonImports Newtonsoft.JsonPublic Class Form1 Public Sub New() ' 此调用是设计器所必需的。 InitializeComponent() ' 在 InitializeComponent() 调用之后添加任何初始化。 Dim contentData As ContentData = New ContentData() With

c语言三种循环结构特点,c语言循环结构(c语言循环结构特点)_weixin_39703926的博客-程序员秘密

1、while循环 while语句的一般形式为:while(表达式)语句。其中表达式是循环条件,语句为循环体。while语句中的表达式一般是关系表达或逻辑表达式,只要表达式的.for语句循环1 for语句一般形式中的各表达式可以省略,但是分号间隔符不能少。需要注意省略表达式1之前要给循环变量赋初值。2 如省略去表达式2或者3则将造成无限循.循环变量,循环条件,循环体。 关键是这三部分的作用是什么?...

CodeForces 545A_AC--我进步的足迹的博客-程序员秘密

Little Susie, thanks to her older brother, likes to play with cars. Today she decided to set up a tournament between them. The process of a tournament is described in the next paragraph.There are n 

cpu超线程优缺点_什么是超线程?超线程对我有用吗?为什么我用了超线程CPU系统性能没有得到多少提升? .请生意经解答..._这位大叔怪怪嘀的博客-程序员秘密

所谓超线程技术(HT)就是利用特殊的硬件指令,把多线程处理器内部的两个逻辑内核模拟成两个物理芯片,从而使单个处理器就能“享用”线程级的并行计算的处理器技术。多线程技术可以在支持多线程的操作系统和软件上,有效的增强处理器在多任务、多线程处理上的处理能力。简单来说就是模拟两个CPU进行工作。采用超线程技术的CPU在处理多任务的能力上显著强过非超线程的CPU,但在单任务的工作方面并没有太大的性能优势,甚...

推荐文章

热门文章

相关标签