hdu 1518(dfs)_.NET_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > .NET > hdu 1518(dfs)

hdu 1518(dfs)

 2014/12/19 16:33:50  敲敲代码,打打酱油  程序员俱乐部  我要评论(0)
  • 摘要:题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1518SquareProblemDescriptionGivenasetofsticksofvariouslengths,isitpossibletojointhemend-to-endtoformasquare?InputThefirstlineofinputcontainsN,thenumberoftestcases.Eachtestcasebeginswithaninteger4<
  • 标签:

题目链接 :http://acm.hdu.edu.cn/showproblem.php?pid=1518

 

 

Square

  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         题意 :给你n条边,让你用这些边组成正方形(不多不少仅n条)。   分析 :主要是超时问题,注意优化。   class="code_img_closed" src="/Upload/Images/2014121916/0015B68B3C38AA5B.gif" alt="" />logs_code_hide('a35daf88-2daa-435e-b445-e915d63dded3',event)" src="/Upload/Images/2014121916/2B1B950FA3DF188F.gif" alt="" />
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 int a[22],vis[22];
 7 int n,m,length;               //length表示要组成的正方形的边长
 8 int ans,flag;
 9 
10 void dfs(int cnt,int sum, int k)   //cnt记录边数,sum记录当前边长,k记录位置
11 {
12     if (cnt == 3)               //如果有三条边满足要求,那么第四条边一定满足要求
13     {
14         flag = 1;
15         return ;
16     }
17     if (sum == length)        //找到满足要求的边,边数加一,初始化
18     {
19         cnt++;
20         k = 0;
21         sum = 0;
22     }
23     for (int i=k; i<m; i++)
24     {
25         if (!vis[i] && sum + a[i] <= length)
26         {
27             vis[i] = 1;
28             dfs(cnt, sum+a[i], i+1);
29             if (flag)         //优化时间,(当找到所有边之后就一直返回,不需要再把之后的代码运行一遍)
30             {
31                 return ;
32             }
33             vis[i] = 0;
34         }
35     }
36 }
37 
38 int main ()
39 {
40     scanf ("%d",&n);
41     while (n--)
42     {
43         ans = 0;
44         scanf ("%d",&m);
45         for (int i=0; i<m; i++)
46         {
47             scanf ("%d",&a[i]);
48             ans += a[i];
49         }
50         if (ans % 4)              //如果所有边长和不是4的倍数,怎样都不能组成正方形
51         {
52             printf ("no\n");
53             continue ;
54         }
55         memset(vis, 0, sizeof(vis));
56         flag = 0;
57         length = ans / 4;     //记录正方形边长
58         dfs(0, 0, 0);
59         if (flag)
60             printf ("yes\n");
61         else
62             printf ("no\n");
63     }
64     return 0;
65 }
View Code

 

 

  • 相关文章
发表评论
用户名: 匿名