K. 冒险公社 （线性DP）

K. 冒险公社 （线性DP） K. 冒险公社 题意：

根据预测情况，求前 n 个岛最多的绿岛数 分析：

没有思路的情况下，先想了一下暴力， O ( 3 n ) O(3^n) O(3n) 显然超时

暴力枚举所有情况，每次都会考虑n个岛的具体颜色

但实际上，对于每次预判我们只需要考虑当前岛和其前两个岛的颜色即可

所以，考虑线性DP，枚举每三个岛的情况，记录状态，再状态转移即可

d p [ i ] [ y ] [ z ] dp[i][y][z] dp[i][y][z] 表示前 i 个岛，第i个岛颜色为z，第i-1个岛颜色为y的情况下，最多绿岛数，那么状态转移方程为，

dp[i][y][z]=max(dp[y][z],dp[x][y]+(z==1));

然后根据当前预测值分为三类情况考虑：（g表示三个岛绿岛数，r表示红岛数）

s[i]==‘R’： r > g r>g r>g 时才会进行状态转移

s[i]==‘G’： g > r g>r g>r 时，~~

s[i]==‘B’： g = = r g==r g==r 时，~~

坑点：最后答案为0时，也是合法情况，因此dp初值要赋为无穷小才能得到非法情况"-1"

#include 
using namespace std;

const int N=1e5+5;
char s[N];
int dp[N][5][5];
void solve()
{
    int n;
    cin>>n>>s+1;
    memset(dp,-0x3f,sizeof(dp));
    // 预处理
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            int g=(i==1)+(j==1), r=(i==2)+(j==2);
            dp[2][i][j]=g;
        }
    }
    for(int i=3;i<=n;i++)
    {
        for(int x=1;x<=3;x++)
            for(int y=1;y<=3;y++)
                for(int z=1;z<=3;z++)
                {
                    int g=(x==1)+(y==1)+(z==1), r=(x==2)+(y==2)+(z==2);
                    if((g==r && s[i]=='B') || (g>r && s[i]=='G') || (g=0) cout<>T;
    while(T--) solve();
}