题解(附带递推公式推导过程)

#include<iostream>
using namespace std;
long long f[50];//i个格子的涂法
int main(){
    int n;
    cin>>n;
    f[0]=0,f[1]=0,f[2]=6;//边界
    for(int i=3;i<=n;i++){
        f[i]=f[i-1]+2*f[i-2];//递推式
    }
    /*
    递推过程
    3个格子的时候最后一个不能和第二个重复，也不能和第一个重复
    所以就是3*2*1种方法
    4个格子的时候要考虑两种情况
    第一种就是前三个格子符合只有三个格子时的要求，也就是3*2*1*(3-1-1)种
    因为只有三种颜色所以这种情况下，最后一个总是一种方法，也就是f[i-1]*1
    第二种就是前三个格子为aba时，也就是3*2*(3-1)种
    aba中如果锁定了第一个a，那么第三个a就不需要考虑了
    而最后一个只要不和a重复就可以了，有两种情况
    而ab正好就是两个格子的情况，也就是2*f[i-2]
    
    最终的递推式就是f[i-1]+2*f[i-2]
    */
    cout<<f[n];//输出
}