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

解题报告：

题目大意：给你一个n，表示有n个排成一条直线的方格，现在有红、粉、绿三种颜色，用着三种颜色将这个n个方格涂满，涂色的规则是相邻的两个方格的颜色不能相同，

并且最后一格跟第一格的颜色不能相同，要求一共有多少涂色的方法。

也是一道动态规划题，若现在要求有n个方格时有多少种涂色方法，可以把它化为两个子问题来 求解，第一，当第n-1个方格涂的颜色与第一格的颜色相同时，而第n-1格的颜色与第一格颜色相同的情况可以由n-2格的结果得到，因为当有n-2个方格的情况的时候，要求的就是最后一格不能与第一格的颜色相同，于是就可以看成是将n-2的情况直接在后面加上一种与第一格相同的颜色，就得到了当第n-1格的颜色与第一格的颜色相同的情况。而当第n-1格的颜色与第一格相同时，第n格的涂色方案就可以是两种了。接下来就考虑另一种子问题，即当第n-1格的颜色与第一格的颜色不同时，那么第n格的涂色方案很明显就只有一种了，于是将这两种子问题加起来就得到有n个方格时涂色方案的种数。

#include<stdio.h>
__int64 DP[55],n;
void dabiao() {
    DP[1]=3;
    DP[2]=DP[3]=6;
    for(int i=4;i<=51;++i)
    DP[i]=DP[i-1]+DP[i-2]*2;
}
int main() {
    dabiao();
    while(scanf("%I64d",&n)!=EOF)
    printf("%I64d\n",DP[n]);
    return 0;
}