【DFS+剪枝】Square

https://www.bnuoj.com/v3/contest_show.php?cid=9154#problem/J

【题意】

给定n个木棍,问这些木棍能否围成一个正方形

【Accepted】

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue> using namespace std;
int n;
const int maxn=;
int a[maxn];
int sum=;
bool vis[maxn];
int flag;
void DFS(int num,int len,int st)
{
if(flag) return;
if(num==)
{
flag=;
return;
}
if(len==sum)
{
DFS(num+,,);
if(flag) return;
}
for(int i=st;i<n;i++)
{
if(!vis[i]&&len+a[i]<=sum)
{
vis[i]=true;
DFS(num,len+a[i],i+);
if(flag)
{
return;
}
vis[i]=false;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,false,sizeof(vis));
sum=;
scanf("%d",&n);
for(int i=;i<n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%!=)
{
puts("no");
continue;
}
sum/=;
flag=;
for(int i=;i<n;i++)
{
if(a[i]>sum)
{
puts("no");
flag=;
break;
}
}
if(flag==) continue;
sort(a,a+n);
flag=;
DFS(,,);
if(flag==)
{
puts("yes");
}
else
{
puts("no");
}
}
return ;
}

DFS+剪枝

上一篇:1317: Square(DFS+剪枝)


下一篇:【审核】检查iOS项目中是否使用了IDFA