題意：求一個長度為n的由0和1組成的序列中滿足沒有兩個1相鄰的序列的數目。
思路：推出前3項後就可以發現滿足斐波那契數列。
代碼：
[cpp]
#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std; www.2cto.com
#define CLR(arr,val) memset(arr,val,sizeof(arr))
long long dp[50];
int main(){
int numcase;
CLR(dp,0);
dp[1] = 2;dp[2] = 3;
for(int i = 3;i < 50;++i)
dp[i] = dp[i-1] + dp[i-2];
scanf("%d",&numcase);
for(int i = 1;i <= numcase;++i){
int n;
scanf("%d",&n);
printf("Scenario #%d:\n",i);
printf("%lld\n\n",dp[n]);
}
return 0;
}
作者：wmn_wmn
