HDU （2045 不容易系列之(3)—— LELE的RPG难题）

题目大意：有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.

题目分析：

这个题目刚刚开始，规律是找出来了，但是边界木有考虑好啊！

首先来分析一下：

假设求N个格子有多少种图法：

1）当N-1个与第一个相同颜色，所以这种图法不合法，从而映射出，第N-2个肯定合法！所以这时候我们有两种图法，即不用考虑第N-1个，只用考虑N-2合法的染法种类数  ： 2*F[ N-2];

2) 当N-1个与第一个不相同，说明从第一个到第N-1个都是合法的图法，我们就不用考虑太多，这里只能用一种颜色了，您想啊，头用了一种颜色，N-1用了一种颜色，第N个既不能与第一个相同，又不能与第N-1个相同，那么只有一种颜色了，这时候只用考虑N-1的长度的合法种类: F[ n-1]

F[ N ] = F[ N-1 ]+2* F [ N-2 ];

但是这里要考虑边界问题！

f[1]=3;

f[2]=6;

f[3]=6;

这里的三个格子比较特殊，因为总公才3种颜色，相邻，头尾颜色各异，所以个数为2的 与格子数为3的 图法一样

代码：

#include<iostream>
#include<cstdio>
using namespace std;
double s[55]={0};
int main(){
	int i,n;
	s[1]=3;
	s[2]=6;
	s[3]=6;
	for(i=4;i<=50;i++)
		s[i]=s[i-2]*2+s[i-1];
	while(scanf("%d",&n)!=EOF){
		printf("%.0lf\n",s[n]);
	}
	return 0;
}