杭电2047 阿牛的EOF牛肉串(递推)
杭电2047 http://acm.hdu.edu.cn/showproblem.php?pid=2047
题目大意:
EOF三个字符排列,要求不出现连续的O字符。
可以这样考虑,对于第n个字符
1.如果该字符为O,第n-1个字符只有两种选择(E F),即有f(n-2)*2 种情况;
2.如果该字符非O,则该字符位,即第n个字符有两种选择(E F),即有f(n-1)*2 种情况。
得到递推式:
f(x-1)*2+f(x-2)*2;
AC代码:
#include<iostream>
using namespace std;
int n;
long long f(int x) {
if(x==1) {
return 3;
}
if(x==2) {
return 8;
}
else {
return f(x-1)*2+f(x-2)*2;
}
}
int main() {
while(cin>>n) {
cout<<f(n)<<endl;
}
return 0;
}