#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真是到一定份兒上的水，但是我還是決定把它貼上來(lái)。
題目大意是用n個(gè)0或者1組成一個(gè)序列，每?jī)蓚€(gè)1不能相鄰，問(wèn)又多少種組成方法。
稍稍考慮了一下，肯定是先考慮第i個(gè)數(shù)的時(shí)候有幾種，第i個(gè)數(shù)嘛，不是0就是1，于是乎，考慮第i-1個(gè)數(shù)，如果第i個(gè)數(shù)放0，那第i-1個(gè)數(shù)放什么都無(wú)所謂，如果第i個(gè)數(shù)放1，那第i-1個(gè)數(shù)就只能放0，貌似這個(gè)狀態(tài)還是非常好確認(rèn)的是吧……
f[i][0]表示第i個(gè)數(shù)是0的時(shí)候，有多少種放法
f[i][1]表示第i個(gè)數(shù)是1的時(shí)候，有多少種放法
根據(jù)前面的推導(dǎo)，f[i][0]=f[i-1][0]+f[i-1][1]，f[i][1]=f[i-1][0]。
然后這道題就沒(méi)有然后了，只是丟人的是……我竟然因?yàn)樯俅蛄艘粋€(gè)回車(chē)錯(cuò)了好幾次……囧……orz。
這道題好象是能證明出來(lái)是個(gè)斐波那切數(shù)列，是不是的我不管了，反正當(dāng)DP做是A了……
好吧，這道題很水其實(shí)，我想的也不慢，繼續(xù)入門(mén)去吧……