HDU2047 阿牛的EOF牛肉串（递推求解）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2047

解题思路：

我们假设n个格子时又f(n)种方案。当前考虑第n个点，如果第n个点时非O那么就只能时E或者F。那么f(n)和f(n-1)的关系是f(n) = 2f(n-1)，因为按照排列组合规律，前n-1个点已经确定时，第n个有几种方案就是总方案数乘几。

如果第n个点是O，那么n-1 一定不是O，只能是E或者F。这样前n-2个就受限制，如果前n-2个确定以后，前n-2，和n-1，n三部分组成的方案数是f(n) = 2f(n-2)

两种情况合起来就是f(n) = 2f(n-1) + 2f(n-2)

code：

#include <cstdio>

using namespace std;
typedef long long LL;

LL s[40+7];
int main()
{
    s[1] = 3;
    s[2] = 8;
    for(int i=3; i<41; i++)
    {
        s[i] = s[i-1] * 2 + s[i-2] * 2;
    }
    int n;
    while(scanf("%d", &n) != EOF)
    {
        printf("%lld\n", s[n]);
    }


    return 0;
}