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(乱搞).

这题n是<=30的 所以我们想到了乱搞.

dfs条件是"该字符不与前两个字符相同".

然后搞出ans*2

[听说这题数学递推Fibonacci].

*/

#include<iostream>

#include<cstdio>

#define MAXN 31

using namespace std;

int n,s[MAXN],len,tot;

void dfs(int t)

{

    if(t==n)

    {

        tot++;

        return ;

    }

    for(int i=0;i<=1;i++)

    {

        if(t>=2&&s[t-1]==i&&s[t-2]==i)  continue;

        s[t]=i,dfs(t+1);

    }

}

int main()

{

    cin>>n;

    if(n) dfs(1);

    printf("%d",tot*2);

    return 0;

}