POJ2362 Square(DFS回溯构造)
http://poj.org/problem?id=2362
题意:给你M根长度可能不同的棍子,问你用着M根棍子能否拼成一个正方形.
分析:首先将M根棍子的总长sum求出,sum%4必须==0且任意一个棍子的长度<=sum/4.
用vis[i]数组表示当前第i根棍子是否被使用了.
然后用dfs来判断能否构成正方形的三边即可.其中dfs(int cnt,int left)表示当前正在构造第cnt根棍子且当前棍子还剩下left长度需要构造.这里注意网上很多解法都是对棍子排序了的,其实不用排序也行.因为我们用到的是定序剪枝,只要棍子的顺序固定就行.
源代码中最重要的剪枝是dfs函数中的begin位置的记录,我们下次搜索所有棍子只需要从begin+1位置开始找即可.为什么?
假设我们当前刚设置完vis[5]=1,表示第5根棍子我们在还是left长度的时候用了,现在我们还是left-len[5]长度的时候要不要去用len[2]来尝试配对一下?不用,肯定无解.因为搜索的时候我们是先找的len[2]的,如果len[2]+len[5]+….
有一个可行解(可以配对成当前cnt边)的话,我们之前肯定已经找到了且推出了dfs这个函数.但是现在明显我们还没找到,所以len[2]+len[5]+…
不可能是一个可行解,所以直接从5后面的位置继续找即可.如果还不能理解,就把本题想象成我们只需要配对一条正方形的边,不用配4边了.
AC代码:110ms
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=25;
int M,sum;//sum表示棍子总长
int len[maxn];
int vis[maxn];
bool dfs(int cnt,int left,int begin)//当前匹配第cnt条边,且该边剩余left长度,且当前轮从begin开始选棍子
{
if(cnt==4) return true;//构造成功
else for(int i=begin;i<M;i++)if(!vis[i])
{
vis[i]=true;
if(left==len[i])
{
if(dfs(cnt+1,sum/4,0)) return true;
}
else if(len[i]<left)
{
if(dfs(cnt,left-len[i],i+1)) return true;
}
vis[i]=false;
}
return false;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
int max_len=0;
sum=0;
scanf("%d",&M);
for(int i=0;i<M;i++)
{
scanf("%d",&len[i]);
max_len=max(max_len,len[i]);
sum+=len[i];
}
if(sum%4!=0||max_len>sum/4)
{
printf("no\n");
continue;
}
//sort(len,len+M); //可以不用排序
memset(vis,0,sizeof(vis));
if(dfs(1,sum/4,0)) printf("yes\n");
else printf("no\n");
}
return 0;
}
分享到:
相关推荐
poj 2362 Square.md
北大POJ2362-Square 解题报告+AC代码
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
poj 1084 Square Destroyer 的AC代码 深度优先搜索 + 启发 未用跳舞链
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
这是POJ上算法学习中推荐的50个题目,熟练编写这些程序,将会使算法水平大有调高
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1014-Dividing【DFS】【多重背包+二进制优化】 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
dfs中的回溯法,poj2488骑士游历,主要是回溯要将所有的点都遍历到。
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友