hdu 4277 USACO ORZ

http://acm.hdu.edu.cn/showproblem.php?pid=4277

　　暴力dfs全部情况，然后用set去重。。。。

　　刚开始的时候打算用状态压缩，先从所有枝条中找到其中两组枝条，枚举全部情况。不过这种方法搜索要15 * 9E7次，一个case就超时了。后来改成枚举3^15种状态的状态压缩，3^15是不超时的，不过统计的时候每种状态统计15次，这就完蛋了！刚开始的时候没有意识到这样的问题，而且状态压缩我也打的不多，所以没有什么时候该用什么时候不该的意识，所以一直TLE都没有找到原因。最后一次代码，在dfs的时候同时统计三条边，然后在用完所有边后用set来统计（或者hash）有多少个不同的三角形，最后输出就好了。

1000ms的代码，囧：

View Code

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <vector>
 5 #include <set>
 6 
 7 using namespace std;
 8 
 9 typedef pair<int, int> pii;
10 typedef pair<pii, int> piii;
11 typedef vector<int> vi;
12 
13 set<piii> tri;
14 vi len;
15 
16 void dfs(int pos, int la, int lb, int lc, int sum){
17     if (pos >= len.size()){
18         if (la <= lb && lb <= lc && la + lb > lc) tri.insert(make_pair(make_pair(la, lb), lc));
19         return ;
20     }
21     if (la + len[pos] <= (sum / 3)) dfs(pos + 1, la + len[pos], lb, lc, sum);
22     if (lb + len[pos] <= (sum >> 1)) dfs(pos + 1, la, lb + len[pos], lc, sum);
23     dfs(pos + 1, la, lb, lc + len[pos], sum);
24 }
25 
26 int main(){
27     int T, n, a, sum;
28 
29 #ifndef ONLINE_JUDGE
30     freopen("in", "r", stdin);
31 #endif
32     scanf("%d", &T);
33     while (T-- && ~scanf("%d", &n)){
34         tri.clear();
35         len.clear();
36         sum = 0;
37 
38         while (n--){
39             scanf("%d", &a);
40             len.push_back(a);
41             sum += a;
42         }
43         dfs(0, 0, 0, 0, sum);
44 
45         printf("%d\n", tri.size());
46     }
47 
48     return 0;
49 }

　　搜索的题做太少了，之后一定要好好加强才行！

——written by Lyon