Problem Description
今年的ACM暑期集训队一共有18人，分为6支队伍。其中有一个叫做EOF的队伍，由04级的阿牛、XC以及05级的COY组成。在共同的集训生活中，大家建立了深厚的友谊，阿牛准备做点什么来纪念这段激情燃烧的岁月，想了一想，阿牛从家里拿来了一块上等的牛肉干，准备在上面刻下一个长度为n的只由"E" "O" "F"三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,阿牛同时禁止在串中出现O相邻的情况，他认为，"OO"看起来就像发怒的眼睛，效果不好。
你，NEW ACMer,EOF的崇拜者，能帮阿牛算一下一共有多少种满足要求的不同的字符串吗？
PS: 阿牛还有一个小秘密，就是准备把这个刻有 EOF的牛肉干，作为神秘礼物献给杭电五十周年校庆，可以想象，当校长接过这块牛肉干的时候该有多高兴！这里，请允许我代表杭电的ACMer向阿牛表示感谢！
再次感谢！
Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数n组成，(0<n<40)。
Output
对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。
Sample Input
Sample Output
Author
lcy
Source
Recommend
lcy | We have carefully selected several similar problems for you:
2048 2050 2049 1297 1290
本题也用动态规划思想，具体分析如下：
有题目可知，串的要求时：
1 串只能含有 ‘E‘,‘O‘,‘F‘三种字符，要么含有单一一种，要么只含有其中的两种，要么三种字符都出现在串中。
2两个‘o‘不能相邻，即不能出现‘oo‘
首先创建一个dp数组，数组下标表示字符个数（即串的长度），元素值表示该长度下所对应满足题目的种数。
由手工排列可得dp[1]=3,dp[2]=8,dp[3]=22; 但是当个数n>=4时，手工排列就比较困难，此时该怎么办呢？
当字符长度为n时第n个字符有三种取值情况 ‘E‘,‘O‘,‘F‘
分类1： 当取‘E‘,‘F‘时，说明第n-1个字符‘E‘,‘O‘,‘F‘都可以取(没有约束条件，也就是dp[i-1]的全部)，因为前n-1长度的字符串有dp[i-1]种，此时第n个字符可取‘E‘,‘F‘，故长度为n的字符串在此分类下有dp[i-1]*2种
分类2： 当取‘o‘时，说明第n-1个字符只能是‘E‘,‘F‘,这时第n-2个字符‘E‘,‘O‘,‘F‘都可以取（没有约束条件，也就是dp[i-2]的全部），因为前n-2长度的字符串有dp[i-2]种，此时第n-1个字符是‘E‘或‘F‘,第n个字符取‘O‘，故长度为n的字符串在此分类下有dp[i-2]*2*1种。
综上所述，符合题目要求长度为n的字符串一共有dp[i-1]*2+dp[i-2]*2种。
C语言代码如下：
#include<stdio.h>
int main()
{
long long dp[100];
int n;
while( scanf("%d",&n) != EOF )
{
dp[1]=3;
dp[2]=8;
for(int i=3;i<=n;i++)
{
dp[i]=(dp[i-1])*2 + (dp[i-2]*2);
}
printf("%lld\n",dp[n]);
}
}
**HDoj 2047 阿牛的EOF牛肉串
原文：https://www.cnblogs.com/wzmm/p/12622255.html
