思路：动态规划。因为不能有连续三个不同的颜色，所以只要看最后三个就可以了。

设dp[n]为长度为n到达彼岸的方案数。

①当第n-2个颜色和第n-1个颜色相同时，第n个位置可以取任意一种颜色，dp[n-1]==dp[n-2]，dp[n] = dp[n-2]*3;

②当第n-2个颜色和第n-1个颜色不同时，第n个位置只要取前两个中的任意一个即可，dp[n-1]-dp[n-2]为第n-1个位置不同的方案数，dp[n] =（dp[n-1]-dp[n-2]）*2。

dp[n] = dp[n-2]*3 +（dp[n-1]-dp[n-2]）*2 = dp[n-1]*2+dp[n-2]

代码：

 

#include
     
      using namespace std;#define ll long long#define pb push_back#define mem(a,b) memset((a),(b),sizeof(a))const int INF=0x3f3f3f3f;const int N=1e5+5;ll dp[40];int main(){    int n;    int c;    dp[1]=3;    dp[0]=3;    for(int i=2;i<40;i++)    {        dp[i]=dp[i-1]*2+dp[i-2];    }    scanf("%d",&c);    while(c--)    {        scanf("%d",&n);        printf("%lld\n",dp[n]);    }    return 0;}