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
*/