1 //Accepted    156 KB    16 ms 2 //dp[i][0]表示一共有i位，最后一位是0的方案数 3 //dp[i][1]表示一共有i位，最后一位是1的方案数 4 //dp[i][1]=dp[i-1][0] 5 //dp[i][0]=dp[i-1][1]+dp[i-1][0] 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 using namespace std;10 const int imax_n = 45;11 int dp[imax_n][2];12 int n;13 void Dp()14 {15     memset(dp,0,sizeof(dp));16     dp[1][0]=dp[1][1]=1;17     for (int i=2;i<imax_n;i++)18     {19         dp[i][0]=dp[i-1][0]+dp[i-1][1];20         dp[i][1]=dp[i-1][0];21     }22 }23 int main()24 {25     Dp();26     int T;27     scanf("%d",&T);28     for (int t=1;t<=T;t++)29     {30         scanf("%d",&n);31         printf("Scenario #%d:\n",t);32         printf("%d\n\n",dp[n][0]+dp[n][1]);33     }34     return 0;35 }