题目
时间限制 1000 ms
内存限制 64 MB
题目描述
有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法，要求对结果取模20141001。
输入数据
多组输入(<=100组数据，读入以EOF结尾)。 每组一行输入一个数字，n(2<=n<=2014) 环形的长度。
输出数据
每组输出一行结果。
样例输入
3样例输出
6思路
定义递归函数：
Color(n):前1到n的格子的染色方案数。
Color（n）有两个条件：
（1）第n个格子不能与第n-1个格子颜色相同
（2）第n个格子不能与第1个格子相同。
递归公式：
由题目可以知道，第n个格子的取色是由第n-1个格子和第1个格子颜色异同情况决定的。
（1）若第n-1个格子和第1个格子相同：
（i）则第n个格子有2个取法。
而此时第n-1个格子的取色情况已经与第1个格子相同，不独立了
（ii）所以之前的方案数是真正自由取色的Color(n-2)。
相乘则总情况数是：2*Color(n-2)
（2）若第n-1个格子和第1个格子不同：
第n个格子只有一个取色。
情况数就是：Color(n-1)
综上：Color(n)=2*Color(n-2)+Color(n-1)
递归终点：
Color(3)=6，Color(2)=6
Q1:为什么以n==3作为递归终点呢。
因为对于3个格子，第一个格子有3个颜色的取法，第二个格子有2个取法
但对于第3个格子，它同时受到第一个格子和第二个格子的限制：
（1）第三个格子不能与第一个格子颜色相同，假设第一个格子是Red，那第三个格子只有Pink和Green可选。
（2）第三个格子也不能与上一个（即第二个格子）相同。而第二个格子也不能与前一个（即第一个格子）相同，所以第二个也只能是Pink和Green的其中之一。假设第二个格子是Pink，那第三个格子不能与一二相同，只能是Green。
对于n>3的情况，第n-1个格子和第1个格子的取色就不会像n==3一样相互牵制。
所以n==3是递归终点。Color(3)=3*2*1=6
Q2:为什么以n==2作为递归终点呢。
n==2也和n==3一样具有特殊性
第2个格子的前一个格子就是第1个格子，条件重叠了，只起到一个效果。
Color(2)=3*2=6
代码
#include<iostream>
#include<cmath>
using namespace std;
#define len 2020
long long int block[len]={0};
long long int color(int n){
if(n==2||n==3) return 6;
else if(block[n]==0) block[n]=(2*color(n-2)+color(n-1))%20141001;
return block[n];
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
cout<<color(n)<<endl;
}
return 0;
}