阿牛的EOF牛肉串
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 12267 Accepted Submission(s): 5769
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
1
2
Sample Output
3
8
又一dp 呵呵 也只有我這種水人來做這麼簡單的dp.
呵呵 那個不容易系列之(3)—— LELE的RPG難題是一樣的吧 太相似了！！！
[cpp]
#include<stdio.h>
#include<iostream>
using namespace std;
#include<algorithm>
__int64 same[51],dif[51];
int main()
{
int i,n;
same[1]=1;
dif[1]=2;
for(i=2;i<=40;i++)
{
same[i]=dif[i-1];//same[i]表示的是i個長度時末尾為o的做法
dif[i]=2*dif[i-1]+same[i-1]*2;//dif[i]表示的是i個長度時末尾不為o的做法
}
while(cin>>n)
{
printf("%I64d\n",dif[n]+same[n]);
}
return 0;
}
