题解 A446.涂色问题

用 a[i] 表示把 i 个格子按要求涂色的涂法，易得：
当 i=1 时，有 1 个格子时有 3 种涂法；当 i=2 时，有 2 个格子时有 6 种涂法；当 i=3 时，有 3 个格子时有 6 种涂法。

当 i≥4 时，假设已经求出 a[1]~a[i−1]，求 a[i]，对于 a[i−1] 有两种情况：
（1）第 i−1 格的涂色合法，即在没有加入第 i 个格子的时候，第 i−1 个格子和第 i−2 个格子颜色不同且和第 1 个格子的颜色也不相同。当加入第 i 个格子，第 i 个格子的颜色已经是确定的。所以此时的方案数为：

a[i−1]×1=a[i−1]

（2）第 i−1 格的涂色不合法(对于整体的 i 个格子依然是合法的)，即在没有加入第 i 个格子的时候，即第 i−1 个格子和第 i−2 个格子颜色不同但是和第 1 个格子的颜色相同。当加入第 i 个格子，第 i 个格子有两种情况。此时的方案数为：

a[i−2]×1×2=2×a[i−2]
分类用加法原理，分步用乘法原理
综合以上两种情况：
a[i]=a[i−1]+2×a[i−2]，i≥4

1、定义变量n,进行输入,定义数组a,进行存储

2、初始条件,1个格子时有3种涂法, 2个格子时有6种涂法,3个格子时有6种涂法

3、递推式:a[i]=a[i-1]+2*a[i-2]

4、输出

#include <iostream>
using namespace std;
long long a[66]; //a[i]:把i个格子 按要求涂色的涂法 
int main() {
	//1、定义变量n,进行输入,定义数组a,进行存储 
	int n;
	cin >> n;
	//2、初始条件,1个格子时有3种涂法, 2个格子时有6种涂法,3个格子时有6种涂法
	a[1] = 3; 
	a[2] = 6; 
	a[3] = 6;
	//3、递推式:a[i]=a[i-1]+2*a[i-2] 
	for(int i = 4; i <= n; i++){
		a[i] = a[i - 1] + 2 * a[i - 2];
	}
	//4、输出 
	cout << a[n]; //输出把 n 个格子按要求涂色的涂法
	return 0;
}