石柱土家族网站建设,惠州室内设计公司排名,介绍网页设计,友情链接出售平台题干#xff1a;
01串
时间限制#xff1a;1000 ms | 内存限制#xff1a;65535 KB
难度#xff1a;2
输入
第一行有一个整数n#xff08;0n100#xff09;,表示有n组测试数据; 随后有n行#xff0c;每行有一个整数m(2m40)#xff0c;表示01串的…题干
01串
时间限制1000 ms | 内存限制65535 KB
难度2
输入
第一行有一个整数n0n100,表示有n组测试数据; 随后有n行每行有一个整数m(2m40)表示01串的长度;
输出
输出不含有“11”子串的这种长度的01串共有多少个占一行。
样例输入
2
2
3样例输出
3
5
描述
ACM的zyc在研究01串他知道某一01串的长度但他想知道不含有“11”子串的这种长度的01串共有多少个他希望你能帮帮他。
注01串的长度为2时,有3种000110。 解题报告 容易推得状态转移方程为dp[i] dp[i-1] dp[i-2];
AC代码
#includebits/stdc.husing namespace std;
int a[500],n;
int main()
{a[0]0;a[1]2;a[2]3;for(int i 3; i 52; i )a[i]a[i-1]a[i-2];int t;cint;while(t--) {cinn;couta[n]endl;}return 0;
}
