版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

?題目：http://acm.hdu.edu.cn/showproblem.php?pid=2510

?

我是通過深搜+回溯然后打表通過的。。。

就是對于‘+’和‘-’的處理上有點難想，這里用到了異或運算。

我們知道1^1=0; 1^0=1, 0^1=1 , 0^0=0;

把-‘-’當(dāng)作1，‘+’當(dāng)作0時；這樣正好滿足題意。?

方便計算

?

?

?

下面分是用DFS的AC代碼和打表代碼：

@@@DFS：

[cpp]?view plaincopy print?

1. #include<iostream>????
2. using?namespace?std;????
3. int?n;????????????????????
4. int?counter;????????????//1計數(shù)，即“-”號計數(shù)???????????
5. int?p[30][30];????????
6. ???
7. int?cnt[30];??
8. ???
9. void?DFS(int?n)??????
10. {????
11. ????int?i,?j;????????????
12. ????if(?n?>?24?)????
13. ????{????
14. ????????return?;?????????????????
15. ????}????
16. ????else???
17. ????{????
18. ???????for(i=0;?i<2;?++i)????
19. ???????{????
20. ????????????p[1][n]?=?i;????????//第一行第n個符號????
21. ????????????counter?+=?i;???????//“-”號統(tǒng)計,因為"+"的值是0???
22. ????????????????
23. ????????????for(j=2;?j<=n;?++j)??//當(dāng)?shù)谝恍蟹?gt;=2時，可以運算出下面行的某些符號，j可代表行號????
24. ????????????{?????
25. ???????????????p[j][n-j+1]?=?p[j-1][n-j+1]^p[j-1][n-j+2];//通過異或運算下行符號，t-j+1確定的很巧????
26. ???????????????counter?+=?p[j][n-j+1];?????????????????????????
27. ????????????}?????
28. ??????????????
29. ????????????if(n*(n+1)/2==2*counter)??
30. ????????????{??
31. ????????????????cnt[n]++;??
32. ????????????}??
33. ??????????????
34. ????????????DFS(n+1);??????????
35. ??????????????
36. ??????????????
37. ????????????for(j=2;?j<=n;?++j)????//回溯，判斷另一種符號情況???像是出棧一樣，恢復(fù)所有對counter的操作??
38. ????????????{????
39. ????????????????counter?-=?p[j][n-j+1];????
40. ????????????}?????????????????????
41. ????????????counter?-=?i;????
42. ???????}????
43. ????}????
44. }????
45. ???
46. int?main()????
47. {???
48. ????counter?=?0;??
49. ??
50. ????DFS(1);??
51. ????while(cin?>>?n,n)??
52. ????{??
53. ????????cout<<cnt[n]<<endl;??
54. ????}???
55. ????return?0;????
56. }??
57. ?????

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

@@@打表代碼：

[cpp]?view plaincopy print?

1. #include?<iostream>???
2. using?namespace?std;?????
3. int?result[24]={0,0,4,6,0,0,12,40,0,0,171,410,0,0,1896,5160,0,0,32757,59984,0,0,431095,822229};???
4. int?main()???
5. {???
6. ????int?n;???
7. ????cin>>n;??
8. ????while(n!=0)??
9. ????{??
10. ????????cout<<n<<"?"<<result[n-1]<<endl;??
11. ????????cin>>n;??
12. ????}??
13. ????return?0;??
14. } ?

總結(jié)

以上是生活随笔為你收集整理的dfs的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。