首页 > 其他 > 详细

hdu 1518 square

时间:2015-02-20 15:14:29      阅读:252      评论:0      收藏:0      [点我收藏+]

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");
        }
    }
}

hdu 1518 square

原文:http://blog.csdn.net/u013497977/article/details/43888421

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!