View Code of Problem 3692

#include<stdio.h>
int main(){
	int n;
	long long a[50];
	while(scanf("%d",&n)!=EOF){
		a[0]=0;
		a[1]=3;
		a[2]=6;           //A(3,2)
		a[3]=6;           //A(3,3)
		for(int i=4;i<=n;i++) {
			a[i]=a[i-1]+2*a[i-2];
		}
		printf("%lld\n",a[n]);
	}
} 


//考虑第n-1个格子：
//1、如果这个格子和第1个格子颜色不同，那么第n个格子只有1种选择，前n-1个格子的选择就是A(n-1)，此时n个格子的选择是1×A(n-1)；
//2、如果这个格子和第1个格子颜色相同，那么第n个格子只有2种选择，前n-2个格子的选择就是A(n-2)，此时n个格子的选择是2×A(n-2)。
//所以，A(n) = 2×A(n-2) + A(n-1)，n >= 4。
//这里需要注意的是，因为我们是考虑第n-1个格子，该格子和第1个格子的颜色可能相同也可能不同，所以n >= 4才可以。
//不然n = 3的话，第n-1 = 3-1 = 2个格子和第一个格子的颜色必然不同，就没有上面这2种情况了，所以要从n >= 4开始推