阿牛从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只由”E” “O” “F”三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,

阿牛同时禁止在串中出现O相邻的情况，他认为，”OO”看起来就像发怒的眼睛，效果不好。你，NEW ACMer,EOF的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？

输入数据包含多个测试实例,每个测试实例占一行,由一个整数n组成，(0<n<40)。

对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

思路

当最后一个为E时，则倒数第二位可以随意，即a[i-1];

同理，当最有一个为F时，倒数第二位也可以随意填，即a[i-1];

当最后一个为O时，就不能随意了，因为倒数第二位不能为O,所以再细分下面两种情况：

第一，当倒数两位为EO时，倒数第三位可以随意填，即a[i-2];

第二，当倒数两位为FO时，倒数第三位也可以随意填，即a[i-2];

此时，已经考虑完所有情况了，所以a[i] = 2*a[i-1] + 2*a[i-2].

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;

long long a[41];

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