hdu 1518 Square (심층 검색 + 가지치기)

제목 링크: http://acm.hdu.edu.cn/showproblem.php?pid=1518
제목 의 대의: 제목 이 준 몇 개의 변 에 따라 정사각형 을 구성 할 수 있 는 지 판단 하고 좋 은 심층 검색 응용 을 하 며 가 지 를 자 르 는 것 에 주의 하여 시간 을 초과 하지 않도록 합 니 다!

 1 #include <iostream>

 2 #include <cstdio>

 3 #include<algorithm>

 4 #include <cstring>

 5 using namespace std;

 6 int ap[30],visit[30];

 7 int l,n;

 8 int dfs(int len,int gen,int iqq)

 9 {

10     if (gen==3)

11         return 1;

12     for(int i=iqq; i<n; i++)

13     {

14         //cout<<visit[len]<<endl;

15         if (!visit[i])

16         {

17             visit[i]=1;

18             if (len+ap[i]==l)

19             {

20                 //cout<<len<<endl;

21                 if(dfs(0,gen+1,0))

22                     return 1;

23             }

24             else if (len+ap[i]<l)

25             {

26                 //cout<<len<<endl;

27                 if(dfs(len+ap[i],gen,i)) return 1;

28             }

29             visit[i]=0;

30         }

31     }

32     return 0;

33 }

34 int main ()

35 {

36     int t,sum;

37     while (cin>>t)

38     {

39         while (t--)

40         {

41             cin>>n;

42             sum=0;

43             //Max=0;

44             for (int i=0; i<n; i++)

45             {

46                 cin>>ap[i];

47                 sum+=ap[i];

48             }

49             memset(visit,0,sizeof(visit));

50             sort(ap,ap+n);

51             if (sum%4==0&&n>=4&&ap[n-1]<=sum/4)

52             {

53 

54                 l=sum/4;

55                 if (dfs(0,0,0))

56                     printf ("yes
");

57                 else

58                     printf ("no
");

59                 //cout<<n<<endl;

60             }

61             else printf ("no
");

62         }

63     }

64 }