题目大意
蒜头君觉得白色的墙面好单调，他决定给房间的墙面涂上颜色。他买了 33 种颜料分别是红、黄、蓝，然后把房间的墙壁竖直地划分成 nn 个部分，蒜头希望每个相邻的部分颜色不能相同。他想知道一共有多少种给房间上色的方案。
例如，当 n=5n=5 时，下面就是一种合法方案。
由于墙壁是一个环形，所以下面这个方案就是不合法的。
输入格式
一个整数 nn，表示房间被划分成多少部分。（1≤n≤501≤n≤50）
输出格式
一个整数，表示给墙壁涂色的合法方案数。
样例输入
4
样例输出
18
dp[n]表示n涂色的合法方案数。(即每个相邻颜色不相同且n和第一个不相同)
1.当n-1和1处颜色不同时，那么n处只能有一种选择。那么这种情况时,dp[n]=dp[n-1]
(n-1个合法方案中每一种都满足情况1)
2.当n-1和1处颜色相同时，那么n处有两种选择。
(这时，n-1与1颜色相同，这种情况共dp[n-2]种：n-2种合法方案后，面再加一个与1处的相同颜色n-1，就是情况2的方案数)
那么，满足一般条件n>3的状态转移方程为：
dp[i]=2*dp[i-2]+dp[i-1];
存在不满足一般条件的特殊情况：(手算即可)
dp[0]=3;
dp[1]=6;
dp[2]=6;
#include<iostream>
#define ll long long//暴力的结果一般很大
using namespace std;
int main(){
ll dp[51];
dp[1]=3;
dp[2]=6;
dp[3]=6;
int n;
cin>>n;
for(int i=4;i<=n;i++){
dp[i]=2*dp[i-2]+dp[i-1];
}
cout<<dp[n];
}