square hdu 1518 pku 2362 zju 1909

题目大意:给定n个变成,问是否可以利用这n根组成一个正方形

解题思路:首先所有边的和如果不能被4整除,肯定不可以.如果最大给定的比边长大也肯定不可以

然后多四个边进行搜索,只要已经搜了三个边都满足条件,第四条边就可以不用搜,肯定满足条件

code:

#include
#include
using namespace  std;

int da[21],sum[21];
bool used[21];
int s,flag,n;

void recur(int p,int len,int last)
{
  int x;
  if(p==4){flag=1;return;}
  if(len>s) return;
  if(len==s)
  recur(p+1,0,n-1);  //注意是n-1
  else
  for(x=last;x>=1&&!flag;x--)  //开始!flag没有导致超时
  {
    if(used[x]==true) continue;
    if(len+sum[x]    if(len+da[x]<=s)
    {
       used[x]=true;
       recur(p,len+da[x],x-1);
       used[x]=false;               
    }                         
  }    
}

int main()
{
    int cas,max,i,len,last;
  scanf("%d",&cas);
  while(cas--)
  {
  scanf("%d",&n);
  s=0;max=0;sum[0]=0;
  for(i=1;i<=n;i++)
  {scanf("%d",&da[i]);s+=da[i];if(da[i]>max) max=da[i];used[i]=false;}
  if(s%4) {printf("no\n");continue;}
  s/=4;
  if(max>s) {printf("no\n");continue;}
  sort(da+1,da+n+1);
  for(i=1;i<=n;i++) sum[i]=sum[i-1]+da[i];
  len=da[n];last=n-1;flag=0;  
  recur(1,len,last);
  if(flag) printf("yes\n");
  else printf("no\n");     
  }   
}