新生周赛——YZJ的牛肉干

题目
描述
今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做YZJ的大佬，在共同的集训生活中，大家建立了深厚的友谊，YZJ准备做点什么来纪念这段激情燃烧的岁月，想了一想，YZJ从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只由"Y" “Z” "J"三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,YZJ学长同时禁止在串中出现ZZ相邻的情况，他认为，"ZZ"看起来就像骂人的话语，影响不好。

你，NEWACMer,YZJ的崇拜者，能帮学长算一下一共有多少种满足要求的不同的字符串吗？

输入

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

输出

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

输入样例 1

1
2

输出样例 1
3
8
思路
简单的递推一下以每一位字母结尾时候的符合要求的数量，
ff[n]就表示以Y结尾时候长度为n的字符串有多少种，
同理，fe[n]表示以J结尾长度为n的字符串有多少种，
fo[n]就是以Z结尾长度为n 的字符串有多少种。
那么
你就可以得到这么一个递推公式：

  ff[i]=ff[i-1]+fe[i-1]+fo[i-1];
  fe[i]=ff[i-1]+fe[i-1]+fo[i-1];
  fo[i]=ff[i-1]+fe[i-1];

<mark>就以第一行为例，当第i位为Y时候，符合要求长度为i的字符串数量肯定等于分别以Y结尾长度为i-1的符合要求字符串和以Z结尾长度为i-1的符合要求字符串数量，还有长度为i-1的以J结尾的符合要求字符串数之和（仔细想想是不是这样），剩下两个也是相同的道理，只不过以Z结尾的时候不能再加上以Z结尾的长度i-1的符合要求字符串，（不能出现ZZ)。
那么长度为n的符合要求字符串数量是不是就等于分别以这三个字母结尾的长度为n的字符串数量之和</mark>

AC代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
long long fe[100],ff[100],fo[100];
int main()
{
    int n;
    fe[1]=1;fo[1]=1;ff[1]=1;

    for(int i=2;i<40;i++)
    {
      ff[i]=ff[i-1]+fe[i-1]+fo[i-1];
      fe[i]=ff[i-1]+fe[i-1]+fo[i-1];
      fo[i]=ff[i-1]+fe[i-1];
    }
        scanf("%d",&n);
        printf("%lld\n",ff[n]+fe[n]+fo[n]);

    return 0;
}