深度優先搜尋 codevs 1065 01字元串

codevs 1065 01字元串

 時間限制: 1 s

 空間限制: 128000 KB

 題目等級 : 黃金 Gold

題目描述 Description

輸出僅有0和1組成的長度為n的字元串，并且其中不能含有3個連續的相同子串。

輸入描述 Input Description

輸入檔案隻有一行一個整數n，表示有0和1組成的字元串的長度。0<=n<=30。

輸出描述 Output Description

輸出檔案隻有一行一個整數，表示所有滿足條件的字元串的個數。

樣例輸入 Sample Input

1

樣例輸出 Sample Output

2

1 /*dfs+暴力檢驗
 2 */
 3 #include<iostream>
 4 using namespace std;
 5 #include<cstring>
 6 #include<cstdio>
 7 char ans[35];
 8 int n,sum=0;
 9 bool check(int l1,int r1,int l2,int r2)
10 {
11     while(l1<=r1&&l2<=r2)
12     {
13         if(ans[l1]!=ans[l2]) return false;
14         l1++;l2++;
15     }
16     return true;
17 }
18 void dfs(int k)
19 {
20     if(k==n+1)
21     {
22         sum++;
23         return;
24     }
25     for(int i=0;i<=1;++i)
26     {
27         ans[k]=i+'0';
28         bool flag=true;
29         for(int j=1;j<=k/3;++j)
30           if(check(k-j+1,k,k-j-j+1,k-j)&&check(k-j+1,k,k-j-j-j+1,k-j-j))
31           {flag=false;
32            break;
33                   }
34         if(flag)
35         {
36              dfs(k+1);
37              ans[k]=0;
38         }      
39         else continue;  
40     }
41 }
42 int main()
43 {
44     scanf("%d",&n);
45     if(n==0)
46     {
47         printf("0");
48         return 0;
49     }
50     dfs(1);
51     printf("%d\n",sum);
52     return 0;
53 }