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

轉載于:https://www.cnblogs.com/LyonLys/archive/2012/09/10/hdu_4277_Lyon.html

總結

以上是生活随笔為你收集整理的hdu 4277 USACO ORZ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。