本文出自：blog.csdn.net/svitter

原题：http://acm.hdu.edu.cn/showproblem.php?pid=2045

题意：中文不用我说了吧。

这个题目的关键就在于递推方程——以及错误的测试数据

首先这个题目就是简单的置换群着色问题——

去除了反转的问题，难一点的大家可以看P197（离散数学，高等教育出版社）

我在做这个题目的时候首先被f [ 1 ]  = 3 困扰了。。拜托，根本不符合题意好吗- =一个格子能说是首尾颜色不同吗？

后来写错了递推方程——f [ n ] = f [ n - 1 ] + 3 * f [ n - 2 ]，把 f [ n - 1 ] 的情况多考虑了一遍- = 。

正确的方程应该是 —— f [ n ] = f [ n - 1 ] + 2 * f [ n - 2 ] , n >= 4; （去除了f [ 1 ] = 3 这个坑爹的干扰。）

写成lln是为了防止超范围——写完以后记得DEBUG一下看看有没有超范围——

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

#define lln long long int

lln f[51];

void ace()

{

    memset(f, 0x3f, sizeof(f));

    int i;

    f[1] = 3;

    f[2] = 6;

    f[3] = 6;

    for(i = 4; i <= 50; i++)

    {

        f[i] = f[i - 1] + 2 * f[i - 2];

    }

    int t;

    while(~scanf("%d", &t))

    {

        printf("%I64d\n", f[t]);

    }

}

int main()

{

    ace();

    return 0;

}