NYOJ252-01串-（数位dp）

252-01串

内存限制:64MB 时间限制:1000ms 特判: No
通过数:33 提交数:49 难度:2

题目描述:

ACM的zyc在研究01串，他知道某一01串的长度，但他想知道不含有“11”子串的这种长度的01串共有多少个，他希望你能帮帮他。

注：01串的长度为2时,有3种：00，01，10。

输入描述:

第一行有一个整数n（0<n<=100）,表示有n组测试数据;

随后有n行，每行有一个整数m(2<=m<=40)，表示01串的长度;

输出描述:

输出不含有“11”子串的这种长度的01串共有多少个，占一行。

样例输入:

2

2

3

样例输出:

3

5

#include<cstring>

#include<algorithm>

#include<stdio.h>

#include<iostream>

#define ll long long

#define inf 0x3f3f3f3f

using namespace std;

ll dp[][];///dp[i][j]表示第i位，以j开头的 符合条件的 01串有多少个

int main()

{

    memset(dp,,sizeof(dp));

    dp[][]=dp[][]=;

    dp[][]=;

    dp[][]=;

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

    {

        dp[i][]=dp[i-][]+dp[i-][];///以0开头后面什么都能加

        dp[i][]=dp[i-][];///以1开头需要i-1位是0,往后的位的可能都包含在i-1位里，不用再加

    }

    int t,n;

    cin>>t;

    while(t--)

    {

        cin>>n;

        printf("%lld\n",dp[n][]+dp[n][]);

    }

    return ;

}

/*

0

1

00

01

10

11

000

001

010

011

100

101

110

111

*/