题目描述 Description
输出仅有0和1组成的长度为n的字符串，并且其中不能含有3个连续的相同子串。
输入描述 Input Description
输入文件只有一行一个整数n，表示有0和1组成的字符串的长度。0<=n<=30。
输出描述 Output Description
输出文件只有一行一个整数，表示所有满足条件的字符串的个数。
样例输出 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 }
原文：http://www.cnblogs.com/c1299401227/p/5592296.html
