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
/*dfs+暴力检验
*/
#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
char ans[];
int n,sum=;
bool check(int l1,int r1,int l2,int r2)
{
while(l1<=r1&&l2<=r2)
{
if(ans[l1]!=ans[l2]) return false;
l1++;l2++;
}
return true;
}
void dfs(int k)
{
if(k==n+)
{
sum++;
return;
}
for(int i=;i<=;++i)
{
ans[k]=i+'';
bool flag=true;
for(int j=;j<=k/;++j)
if(check(k-j+,k,k-j-j+,k-j)&&check(k-j+,k,k-j-j-j+,k-j-j))
{flag=false;
break;
}
if(flag)
{
dfs(k+);
ans[k]=;
}
else continue;
}
}
int main()
{
scanf("%d",&n);
if(n==)
{
printf("");
return ;
}
dfs();
printf("%d\n",sum);
return ;
}