HDU-2045

沿用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;
}