hdu 1518 square

Square

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 9502    Accepted Submission(s): 3091

Problem Description Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input The first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.

Output For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

Sample Input

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5
        

Sample Output

yes
no
yes
  
  

  
  
          
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define maxn 1005
int m;
int a[maxn];
int ss;
bool vis[maxn];
bool flag;
void dfs(int dep,int sum,int cnt){
   if(sum>ss)return ;
   if(sum==ss){
    dep=0;
    cnt++;
    sum=0;
    if(cnt==3){flag=1;return;}
   }
   if(flag)return ;
   for(int i=dep;i<m;i++){
        if(flag)return;
    if(!vis[i]){
        vis[i]=1;
        dfs(i,sum+a[i],cnt);  //一开始第一个参数写成了dep+1，结果一直tle
        vis[i]=0;
        if(flag)return;
        //while(a[i]==a[i+1]&&i<m)i++;
    }
   }
}
int main()
{
    int n;
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    while(n--){
        scanf("%d",&m);
        ss=0;
        memset(vis,0,sizeof vis);
        for(int i=0;i<m;i++){
            scanf("%d",&a[i]);
            ss+=a[i];
        }
        flag=0;
        if(ss%4!=0)puts("no");
        else{
            ss=ss/4;
            dfs(0,0,0);
            if(flag==0)puts("no");
            else puts("yes");
        }
    }
}