square.cpp

哈工程大学oj上的1002

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdlib.h>

int n; 
int stick[30]; 
int total; 
int ns; 
int ok; 
int len; 

int cmp(const void *a,const void *b) { 
   int a1 = *(int *)a; 
   int a2 = *(int *)b; 
   return a2 - a1; 
} 
int used[30]; 

int adds() { 
   int j = 0; 
   for (int i = 1;i <= n;i++) 
      j += stick[i]; 
   return j; 
} 

void search(int,int,int); 

void s(int x) { 
   if (x > 4) { 
        ok = 1; 
      //printf("%d\n", len); 
      return; 
   } 
   if(ok) return;
   int i; 
   for (i = 1;i <= n;i++) 
      if (!used[i]) break; 

   used[i] = 1; 
   search(x,stick[i],i); 
   used[i] = 0; 
} 

void search(int num,int now,int next) { 

   if (ok) return; 
   if (now == len) { 
       s(num + 1); 
    return; 
   } 

   if (next>n) return; 

   for (int i = next + 1;i <= n;i++) {
      if(ok) return;
      if (!used[i]) 
       if(stick[i] + now <= len) { 
         used[i] = 1; 
         search(num,now + stick[i],i); 
         used[i] = 0;  
       } 
   } 
}

int main () {
   int k=0;
   int N; 
   scanf("%d",&N);//printf("%d\n",N);
   while (k<N&&scanf("%d", &n)==1) { //printf("%d\n",n);
       //if (!n) break; 
       ok = 0;         
       int i; 
       for (i = 1;i <= n;i++) 
       scanf("%d", &stick[i]); //printf("%d\n",stick[i]);}
       qsort(stick+1,n,sizeof(int),cmp); 
       //for (i = 1;i <= n;i++)  printf("%d\n",stick[i]);
       total = adds(); 
       //ns = total / i; 
       if(total%4!=0)
       goto output;
       memset(used,0,sizeof(used)); 
       len = total/4; 
       s(1);   
       output:   if(ok==1)
           printf("yes\n");
              else
           printf("no\n");
       k++;
    //printf("%d,,,,,",k); 
   }
   system ("pause");
   return 0; 
}