9.6腾讯音乐笔试第二题可爱串 2（3）维dp

思路：先统计所有的含red子串的可能（可连续可不连续)，然后统计含连续red的可能，前者减去后者。

前者设计4个状态，对应ABCD，分别是：A没出现r，B前面仅出现r，C，前面以此出现re。D依次出现red

A【i】【j】的含义：i取012代表分别red结尾，j代表序列长度-1，A表示这样的取值所处状态，注意有一些矩阵由于违反规定一直是0，可以不更新。

ABCD中有若干转移方程，注意特殊情况，可以从上级转移到下级，否则，只能同级转换。代码未取模。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
class Solution
{
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */


    int kawaiiStrings(int n)
    {
        long long A[3][n];//前面无r
        long long B[3][n];//出现r        
        long long C[3][n];//出现re        
        long long D[3][n];//出现red        
        
        memset(A, 0, sizeof(A));
        memset(B, 0, sizeof(B));
        memset(C, 0, sizeof(C));
        memset(D, 0, sizeof(D));
        //cout << "OK";
        A[0][0]=0;
        A[1][0]=1;       //e
        A[2][0]=1;       //d
        
        B[0][0]=1;       //r
        
        B[2][1]=1;      //rd
        
        C[1][1]=1;      //re
        
        D[2][2]=1;      //red
        
        
        //C[2][2]=1;

        //cout << "OK";
        
        
        for (int i=1;i<n;i++){
            //A[0][i]=0;
            A[1][i]=A[1][i-1]+A[2][i-1];
            A[2][i]=A[2][i-1]+A[1][i-1];      
            
            B[0][i]=B[2][i-1]+B[0][i-1]+A[1][i-1]+A[2][i-1];
            //B[1][i]=0;
            B[2][i]=B[2][i-1]+B[0][i-1];
            
            C[0][i]=C[0][i-1]+C[1][i-1];
            C[1][i]=C[1][i-1]+C[0][i-1]+B[0][i-1]+B[2][i-1];
            //C[2][i]=0;
            
            D[0][i]=D[0][i-1]+D[1][i-1]+D[2][i-1];
            D[1][i]=D[1][i-1]+D[0][i-1]+D[2][i-1];
            D[2][i]=D[2][i-1]+C[1][i-1]+D[0][i-1]+D[1][i-1]+C[0][i-1];
      
        }
        
        long long ans = 0;
        for (int i = 0; i < 3; ++i)
            ans = (ans + D[i][n-1]) ;
        
        //没有连续red    
        long long no_red[n+1];
        memset(no_red, 0, sizeof(no_red));
        no_red[0]=1;
        no_red[1]=3;
        no_red[2]=9;
        for (int i=3;i<=n;i++)
            //没有连续red  
            no_red[i] = (no_red[i - 1] * 3 - no_red[i - 3]);
        //有连续red   
        //print(pow(3,n)-no_red[n])

            
        return ans-((pow(3,n)-no_red[n]));
    }
};
int main()
{
    Solution S;
    int n;
    cin>>n;
    cout << S.kawaiiStrings(n);
    return 0;
}