/**************************************
Problem: HEU 1011 Square
Time: 0.0400 s
Memory: 232 k
Accepted Time: 2009-03-22 14:08:04
Tips: 深度优先搜索 http://acm.hrbeu.edu.cn/forums/index.php?showtopic=2305&hl=1011
**************************************/
#include <stdio.h>
#include <string.h>
int sign,ave,length;
int a[100],table[100];
void dfs(int start,int sum,int flag)
{
if(flag==4){sign=1;return;}
else if(sign==0)
{
if(sum==ave)dfs(0,0,flag+1);
else for(int i=start;i<length;i++)
{
if(table[i]==0&&sum+a[i]<=ave)
{
table[i]=1;
dfs(i+1,sum+a[i],flag);
table[i]=0;
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i,j,k,sum=0;
scanf("%d",&length);
for(i=0;i<length;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%4!=0){printf("no\n");continue;}
for(i=0;i<length-1;i++)
{
k=i;
for(j=i+1;j<length;j++)
if(a[k]<a[j])k=j;
if(k!=i)
{int tt=a[k]; a[k]=a[i]; a[i]=tt;}
}
ave=sum/4;
if(a[0]>ave){printf("no\n");continue;}
memset(table,0,sizeof(table));
sign=0;
dfs(0,0,1);
if(sign)printf("yes\n");
else printf("no\n");
}
return 0;
}
Problem: HEU 1011 Square
Time: 0.0400 s
Memory: 232 k
Accepted Time: 2009-03-22 14:08:04
Tips: 深度优先搜索 http://acm.hrbeu.edu.cn/forums/index.php?showtopic=2305&hl=1011
**************************************/
#include <stdio.h>
#include <string.h>
int sign,ave,length;
int a[100],table[100];
void dfs(int start,int sum,int flag)
{
if(flag==4){sign=1;return;}
else if(sign==0)
{
if(sum==ave)dfs(0,0,flag+1);
else for(int i=start;i<length;i++)
{
if(table[i]==0&&sum+a[i]<=ave)
{
table[i]=1;
dfs(i+1,sum+a[i],flag);
table[i]=0;
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int i,j,k,sum=0;
scanf("%d",&length);
for(i=0;i<length;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
if(sum%4!=0){printf("no\n");continue;}
for(i=0;i<length-1;i++)
{
k=i;
for(j=i+1;j<length;j++)
if(a[k]<a[j])k=j;
if(k!=i)
{int tt=a[k]; a[k]=a[i]; a[i]=tt;}
}
ave=sum/4;
if(a[0]>ave){printf("no\n");continue;}
memset(table,0,sizeof(table));
sign=0;
dfs(0,0,1);
if(sign)printf("yes\n");
else printf("no\n");
}
return 0;
}