hdu 1518 dfs+剪定

数本の棒が正方形Sample Input 3//テストグループ数4 1 1 1 1//棒の数と1本の棒の長さ5 10 20 30 40 508 1 7 2 6 4 4 3 5 Sample Outputyesnoyes
 
posを使わずに直接0から列挙しても答えはありますが、タイムアウトしたり、posを付けたりして、以前dfsが過ぎた場合は二度と現れません.以前のbcの問題を思い出してもそうです.

 1 #include<cstdio>

 2 #include<iostream>

 3 #include<algorithm>

 4 #include<cstring>

 5 #include<cmath>

 6 #include<queue>

 7 #include<map>

 8 using namespace std;

 9 #define MOD 1000000007

10 const int INF=0x3f3f3f3f;

11 const double eps=1e-5;

12 #define cl(a) memset(a,0,sizeof(a))

13 #define ts printf("*****
");

14 const int MAXN=1005;

15 int n,m,tt;

16 int a[30];

17 bool vis[30];

18 int len1;

19 bool dfs(int len,int pos,int tot)

20 {

21     if(tot==4)  return 1;

22     for(int i=pos;i<n;i++)

23     {

24         if(vis[i])  continue;

25         if(len+a[i]==len1)

26         {

27             vis[i]=1;

28             if(dfs(0,0,tot+1))  return 1;

29             vis[i]=0;

30         }

31         if(len+a[i]<len1)

32         {

33             vis[i]=1;

34             if(dfs(len+a[i],i,tot))   return 1;

35             vis[i]=0;

36         }

37     }

38     return 0;

39 }

40 int main()

41 {

42     int i,j,k;

43     #ifndef ONLINE_JUDGE

44     freopen("1.in","r",stdin);

45     #endif

46     scanf("%d",&tt);

47     while(tt--)

48     {

49         scanf("%d",&n);

50         len1=0;

51         for(i=0;i<n;i++)

52         {

53             scanf("%d",&a[i]);

54             len1+=a[i];

55         }

56         if(len1%4!=0||n<4)      // 4 4 

57         {

58             printf("no
");

59             continue;

60         }

61         len1/=4;

62         sort(a,a+n);

63         memset(vis,0,sizeof(vis));

64         if(dfs(0,0,0))  printf("yes
");

65         else printf("no
");

66     }

67 }