2022牛客寒假算法基础集训营1 K.冒险公社 DP

思路

从题目中可以读到：给定的预测结果与 i , i − 1 , i − 2 i,i-1,i-2 i,i−1,i−2有关且前 2 2 2点无法预测，如果要得到最多的绿岛数量，那么我们应该考虑枚举所有可能的构成序列。

定义 d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示考虑到第 i i i个字符，当前结尾的三个字符 i , i − 1 , i − 2 i,i-1,i-2 i,i−1,i−2分别存放了 j , k , l ( ∈ { 1 , 2 , 3 } ) j,k,l(\in\{1,2,3\}) j,k,l(∈{1,2,3})时的最大绿岛数，可以得到转移方程:（注意要初始化不可以是 0 0 0，因为 0 0 0也属于合法情况） d p [ i ] [ j ] [ k ] = max ⁡ ( d p [ i − 1 ] [ j ] [ k ] , d p [ i − 1 ] [ k ] [ l ] + ( j = = 2 ) ) dp[i][j][k] = \max(dp[i - 1][j][k], dp[i - 1][k][l] + (j == 2)) dp[i][j][k]=max(dp[i−1][j][k],dp[i−1][k][l]+(j==2)) 在转移过程中，需要排掉不符合实际情况的状态：

a[i] == 'R' 要求 c n t R > c n t G cnt_R > cnt_G cntR​>cntG​

a[i] == 'G' 要求 c n t G > c n t R cnt_G > cnt_R cntG​>cntR​

a[i] == 'B' 要求 c n t R = c n t G cnt_R = cnt_G cntR​=cntG​

Accepted Code

#include 
using namespace std;

const int N = 1e5 + 10;
char a[N];
int dp[N][3][3]; 

inline void solve(){
    int n = 0; cin >> n >> a + 1;
    memset(dp, -0x3f, sizeof dp);
    for(int i = 0; i