hdu 1518 Square(深搜+剪枝)

时间:2021-10-30 04:40:49

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1518

题目大意:根据题目所给的几条边,来判断是否能构成正方形,一个很好的深搜应用,注意剪枝,以防超时!

 #include <iostream>
#include <cstdio>
#include<algorithm>
#include <cstring>
using namespace std;
int ap[],visit[];
int l,n;
int dfs(int len,int gen,int iqq)
{
if (gen==)
return ;
for(int i=iqq; i<n; i++)
{
//cout<<visit[len]<<endl;
if (!visit[i])
{
visit[i]=;
if (len+ap[i]==l)
{
//cout<<len<<endl;
if(dfs(,gen+,))
return ;
}
else if (len+ap[i]<l)
{
//cout<<len<<endl;
if(dfs(len+ap[i],gen,i)) return ;
}
visit[i]=;
}
}
return ;
}
int main ()
{
int t,sum;
while (cin>>t)
{
while (t--)
{
cin>>n;
sum=;
//Max=0;
for (int i=; i<n; i++)
{
cin>>ap[i];
sum+=ap[i];
}
memset(visit,,sizeof(visit));
sort(ap,ap+n);
if (sum%==&&n>=&&ap[n-]<=sum/)
{ l=sum/;
if (dfs(,,))
printf ("yes\n");
else
printf ("no\n");
//cout<<n<<endl;
}
else printf ("no\n");
}
}
}