HDU2045_LELE的RPG难题

题目大意： 有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法. 解题思路： WA了两次，找错了规律。 当n>3时，list[i]=list[i-1]+list[i-2]*2; 看来还是找递推规律比较靠谱。 递推思路： 考虑长为n的串，以s[i]表示i位的字符。 1.若前n-1位组成的串合法，则由于首尾不同，再添加一位时，只有1种方法；即s[n] = s[n-1] 2.若前n-1位组成的串不合法，再添加一位后合法，即因为首尾相同而引起的不合法，那么前n-2位组成的串必定合法。此时第n位有2种添加方法。即s[n] = 2*s[n-2] 3.边界条件：f(1)=3;f(2)=6;f(3)=6。参考：http://www.x2studio.net/i/?p=11

#include
using namespace std;
const int MAX = 51;
int main(void)
{
	__int64 f[MAX];
	f[1] = 3;
	f[2] = 6;
	f[3] = 6;//注意这个边界容易错，想象当n=1的时候其实是不满足f[n-2]的那种想法的
	for(int i = 4; i < MAX; i++)
	{
		f[i] = f[i-1] + f[i-2] * 2;
	}
	int n;
	while(scanf("%d", &n) == 1)
		printf("%I64d\n", f[n]);
	return 0;
}