学步园

这个题要分为两种情况，一种是以O结束，一种不是以O结束，定义一个二维数组a[41][2]，将以O结束的放在a[  ][0]中，不是以O结束的放在a[  ][1]中，然后找出以后没每增加1后是不是一O为结束的情况，找出规律，就可以了。

#include<stdio.h>
int main()
{
    long long dp[47][3]={{0,0},{1,2}};
    for (int a=2;a<41;a++)
    {
        dp[a][0]=dp[a-1][1];
        dp[a][1]=2*(dp[a-1][0]+dp[a-1][1]);
    }
    int n;
    while (scanf("%d",&n)!=EOF)
        printf("%lld\n",dp[n][0]+dp[n][1]);
    return 0;
}