#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個數(shù)的時候有幾種，第i個數(shù)嘛，不是0就是1，于是乎，考慮第i-1個數(shù)，如果第i個數(shù)放0，那第i-1個數(shù)放什么都無所謂，如果第i個數(shù)放1，那第i-1個數(shù)就只能放0，貌似這個狀態(tài)還是非常好確認的是吧……
f[i][0]表示第i個數(shù)是0的時候，有多少種放法
f[i][1]表示第i個數(shù)是1的時候，有多少種放法
根據(jù)前面的推導，f[i][0]=f[i-1][0]+f[i-1][1]，f[i][1]=f[i-1][0]。
然后這道題就沒有然后了，只是丟人的是……我竟然因為少打了一個回車錯了好幾次……囧……orz。
這道題好象是能證明出來是個斐波那切數(shù)列，是不是的我不管了，反正當DP做是A了……
好吧，這道題很水其實，我想的也不慢，繼續(xù)入門去吧……