不容易系列之(3)—— LELE的RPG难题

Problem Description
人称“AC女之杀手”的超级偶像LELE最近忽然玩起了深沉，这可急坏了众多“Cole”（LELE的粉丝,即"可乐"）,经过多方打探，某资深Cole终于知道了原因，原来，LELE最近研究起了著名的RPG难题:

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

以上就是著名的RPG难题.

如果你是Cole,我想你一定会想尽办法帮助LELE解决这个问题的;如果不是,看在众多漂亮的痛不欲生的Cole女的面子上,你也不会袖手旁观吧?

Input
输入数据包含多个测试实例,每个测试实例占一行,由一个整数N组成，(0<n<=50)。

Output
对于每个测试实例，请输出全部的满足要求的涂法，每个实例的输出占一行。

Sample Input
1
2

Sample Output
3
6

解题思路：
关于这个题我们从前面往后面推，我们假设我们不知道n，先满足（相邻的方格不能同色）这个条件可以列一个表容易发现它是f(x)=2n这样增长的，然后列一个表n=3时，首尾两格也同色有6种情况，但是当n=4是，这6种情况它就变得“良性”了，因为当n=4时，n-1是和首节相同的，即n-1觉对不可能再相同了，因此有两种选择，其他的只有一种选择，但是我们在这里假设其它的也有两种选择，先列举出来，然后再减去，最后有18种结果满足情况，以后也是这样循环操作，我这里列了一张表。
| 2n | 3 || 6 | 12 || 24 || 48 ||
| 输出 | 3 | 6 | 6 | 18 | 30 |
很容易发现
a[i]=2*n-a[i-1]
知道这个规律很快就能写出代码了。（当然这只是我自己的解题方案，提供一个参考，并不一定是最优的方案，欢迎有更好的方案和我交流）

个人代码如下（c++）：

#include<iostream>
#define max 1000
using namespace std;
long long int a[max];
int main()
{
	long long int n;
	while(cin>>n)
	{
		long long int count=12;
		for(int i=0;i<n;i++)
		{
			if(i==0)
			a[i]=3;
			else if(i==1||i==2)
			a[i]=6;
			else 
			{
				count*=2;
				a[i]=count-a[i-1];
			}
		}
		cout<<a[n-1]<<endl;
	}
}