dfs

版权声明：本文为博主原创文章，未经博主允许不得转载。

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

 

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

就是对于‘+’和‘-’的处理上有点难想，这里用到了异或运算。

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

把-‘-’当作1，‘+’当作0时；这样正好满足题意。 

方便计算

 

 

 

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

@@@DFS：

[cpp] view plaincopy print?

1. #include<iostream>    
2. using namespace std;    
3. int n;                    
4. int counter;            //1计数，即“-”号计数           
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;       //“-”号统计,因为"+"的值是0   
22.                 
23.             for(j=2; j<=n; ++j)  //当第一行符号>=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)    //回溯，判断另一种符号情况   像是出栈一样，恢复所有对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. }  

总结

以上是生活随笔为你收集整理的dfs的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。