#include <stdio.h>
int main()
{
int m, n, f[46][2], i, t = 1;
scanf("%d", &m);
while (t <= m)
{
scanf("%d", &n);
f[1][0] = 1;
f[1][1] = 1;
for (i = 2; i <= n; i++)
{
f[i][0] = f[i - 1][0] + f[i - 1][1];
f[i][1] = f[i - 1][0];
}
printf("Scenario #%d:\n%d\n\n", t++, f[n][0] + f[n][1]);
}
return 0;
}
好吧，我真心知道，这道DP真是到一定份儿上的水，但是我还是决定把它贴上来。
题目大意是用n个0或者1组成一个序列，每两个1不能相邻，问又多少种组成方法。
稍稍考虑了一下，肯定是先考虑第i个数的时候有几种，第i个数嘛，不是0就是1，于是乎，考虑第i-1个数，如果第i个数放0，那第i-1个数放什么都无所谓，如果第i个数放1，那第i-1个数就只能放0，貌似这个状态还是非常好确认的是吧……
f[i][0]表示第i个数是0的时候，有多少种放法
f[i][1]表示第i个数是1的时候，有多少种放法
根据前面的推导，f[i][0]=f[i-1][0]+f[i-1][1]，f[i][1]=f[i-1][0]。
然后这道题就没有然后了，只是丢人的是……我竟然因为少打了一个回车错了好几次……囧……orz。
这道题好象是能证明出来是个斐波那切数列，是不是的我不管了，反正当DP做是A了……
好吧，这道题很水其实，我想的也不慢，继续入门去吧……