题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2047
思路:递推,对下一个要刻的字符进行讨论:EF的下一个字符可能为EOF,O的下一个字符可能为EF。
代码:
#include <stdio.h>
int main()
{
int n, i;
while (scanf("%d", &n) != EOF)
{
long long ef=3, o=0,t;
for (i = 1; i < n; i++)
{
t = ef;
ef = o * 3 + t * 2;
o = t / 3 * 2;
}
printf("%lld\n", ef + o)
}
return 0;
}
/*
计算过程:
3=2+1
8=2*3+1*2
22=2*3*1/3*2+2*3*2/3*3+3*1/3*2*3
......
*/