hdu 1518(dfs)

タイトルリンク: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本だけです).
 
分析:主にタイムアウトの問題で、最適化に注意します.
 

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

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

61         else

62             printf ("no
");

63     }

64     return 0;

65 }

View Code