题意:给你n个0或者1,组成0和1的序列,1和1不能相邻,问有多少种不同的排列,相当水的一题,AC吧,加油。
状态转移方程: dp[i][1] = dp[i-1][0];
dp[i][0] = dp[i-1][0]+dp[i-1][1];
#include<cstdio> #include<cstring> #include<iostream> #define max(a1,b1) (a1)>(b1)?(a1):(b1) #define N 46 using namespace std; int dp[N][2],n; void ini() { memset(dp,0,sizeof(dp)); dp[1][1] = dp[1][0] = 1; for(int i=2;i<N;++i) { dp[i][1] = dp[i-1][0]; dp[i][0] = dp[i-1][0]+dp[i-1][1]; } } int main(void) { int test; ini(); int v = 0; cin>>test; while(test--) { cin>>n; int ans = dp[n][0]+dp[n][1]; cout<<"Scenario #"<<++v<<":"<<endl; cout<< ans<<endl<<endl; } return 0; }