DFS HDU 1518 Square

因为n<=20,较小，用DFS，但是要剪枝，不然就TLE

这个题是校队讨论时ZZM说的，然后里面有讲到一种错误的思路，用0-1背包恰好背满边长，边长的2倍，边长的三倍，边长的四倍

事实上，如果数据是7 7 2 1 7 8就是一个反例，每种都能背满，但是无法构成四边形。

然后我自己先写了一个DFS，用四个数d1,d2,d3,d4来存状态，对于每根棍子，有四种可能，分别是放d1,d2,d3,d4里，再往里搜，回退的时候，d1,d2,d3,d4回到原来的状态。

一个剪枝是当d1,d2,d3,d4中出现大于边长的值就return,不往下搜了。

还有就是已经搜到可行解了，也不搜了。

这样最坏情况下复杂度为O(4^n).很高，一直T，剪枝也不行，我认为我自己的DFS可能很搓，因为貌似复杂度被乘了一个4！，对于这四个数有一个全排列的重复。

不过胜在想法自然。

接着我就百度了别人的代码，大概就是令设一个数组b[],用来记录哪条边被用过了，然后用没有用过的边去构造一条值为正方形边长的边。

DFS中的第一个参数是从哪个点开始找，边的长度< 边长时，按顺序往后搜，别再从0开始搜了``

还有就是找到三条边就够了，剩下的一条边就用剩下的棍子拼就行。

真的感觉自己对DFS理解还是不够深刻，得努力

贴代码：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 bool flag;
 4 int p[22];
 5 int n;
 6 int bc;//边长
 7 bool b[22];
 8 void dfs(int x,int len,int cnt)
 9 {
10     if(cnt == 3)
11     {
12         flag= true;
13         return;
14     }
15     if(flag)
16         return;
17     for(int i= x; i<n; ++i)
18     {
19         if(!b[i] && len+p[i] <= bc)
20         {
21             b[i] = 1;
22             if( len+p[i] == bc)
23                 dfs(0,0,cnt+1);
24             else
25                 dfs(i+1,len+p[i],cnt);
26             b[i] = 0;
27         }
28     }
29 }
30 int main()
31 {
32 //    freopen("in.cpp","r",stdin);
33     int T;
34     scanf("%d",&T);
35     while(T--)
36     {
37         scanf("%d",&n);
38         int sum = 0;
39         for(int i=0; i<n; ++i)
40         {
41             scanf("%d",&p[i]);
42             sum += p[i];
43         }
44         if(sum != sum/4*4)
45         {
46             printf("no\n");
47             continue;
48         }
49         bc = sum/4;
50         flag = false;
51         memset(b,false,sizeof(b));
52         dfs(0,0,0);
53         if(flag)
54             printf("yes\n");
55         else
56             printf("no\n");
57     }
58     return 0;
59 }