沿用HDU-2050的思路，这个也是一个递推的问题。
那么同样的，我们认为答案为f(n)，然后试图通过f(n-1)来求得答案。
不过在这里我们可以把问题做一些分割。
在此之前先给颜色编号：R为0，P为1，G为2。
那么，我们假设格子数为n，并且开头的颜色为i，结尾的颜色为j的时候，并且去除首尾颜色不同这个限制的情况下，方案数为dp[n][i][j]。
于是显然的，答案f(n)就可以这么计算：
f[n]=0;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(i==j)continue;
f[n]+=dp[n][i][j];
}
为什么要去除限制呢？因为我们接着使用的是递推，也就是说首项需要有东西（至少要非全零吧，如果是全零的话万一推下来的东西都是零不就没意义了？）。但是显然的，在没去除限制的情况下，当n=1的时候是全零的。为了避开这种情况所以去除了这个限制，而是等到计算f[n]的时候再加回去。
那么我们接着讨论的就是如何计算dp[n][i][j]。这里使用的是类似于数学归纳法的思想。
首先，我们先讨论n=1的情况。这个的话显然开头的颜色要跟结尾的颜色相同。于是就可以得到这样的初始化方式：
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(i==j)dp[1][i][j]=1;
else dp[1][i][j]=0;
}
好的，接着就是，已知dp[n]的所有9种情况，如何计算dp[n+1]的九种情况。
我们以dp[n][1][2]为例。
首先，dp[n][1][2]有多少种加方格的选择使得其能顺利延展到n+1呢？显然，只要不是2就行了。于是就会有：
dp[n+1][1][0]+=dp[n][1][2];
dp[n+1][1][1]+=dp[n][1][2];
好的，那么把所有的情况都枚举一遍，就可以得到如下代码：
// 假设dp[n+1]全员均为0
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
{
if(j==k)continue;
dp[n+1][i][k]+=dp[n][i][j];
}
于是拼接起来就可以得到我们最终的代码了：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[55];
LL dp[55][5][5];
void init()
{
memset(f,0,sizeof(f));
memset(dp,0,sizeof(dp));
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(i==j)dp[1][i][j]=1;
else dp[1][i][j]=0;
}
for(int n=1;n<50;n++)
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
{
if(j==k)continue;
dp[n+1][i][k]+=dp[n][i][j];
}
for(int n=2;n<=50;n++)
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
{
if(i==j)continue;
f[n]+=dp[n][i][j];
}
// 特殊情况，我也不知道为什么只有一块的时候答案是3，但是它样例都这么给了就特判一下吧
f[1]=3;
}
int main()
{
init();
int n;
while(~scanf("%d",&n))
{
printf("%lld\n",f[n]);
}
return 0;
}
