HDU2045

递推思路：记f(n)为n个格子的方法数目。在前面n-1个格子已经调好的情况下，填第n个格子。满足条件的n个格子的填色方法有两种情况。第一种情况是，第1格和第n-1格颜色不相同，那么可以在此基础上只选一个颜色，也就是f(n-1)种。第二种情况是，第1格和第n-1格颜色相同，那么可以在此基础上选两种，此基础对应的数目可以这么考虑，它是n-2个格子的基础上，在n-1格填1格的颜色得来的，也就是这种情况的基础数量是f(n-2)种，故第二种情况对应的数目为2*f(n-2)

#include <cstdio>

int main()
{
    int n;
    long long ans[60] = {};
    ans[1] = 3;
    ans[2] = 6;
    ans[3] = 6;
    for(int i = 4; i <= 55; i++)
      ans[i] = ans[i-1] + 2 * ans[i-2];
    while(scanf("%d",&n)!=EOF)
    {
        printf("%lld\n",ans[n]);
    }
    return 0;
}