冒险公社,md

#include

using namespace std;
const int N = 1e5 + 10;

int n;
int dp[N][30];
char s[N];

int cal(int x) {
   int g = (x % 3 == 0) + (x / 3 % 3 == 0) + (x / 9 % 3 == 0);
    int r = (x % 3 == 2) + (x / 3 % 3 == 2) + (x / 9 % 3 ==2);
    return g - r;
}
int main () {
    cin >> n;
    cin >> (s + 1);
    for (int i = 0; i <= n; i ++)
        for (int j = 0; j < 27; j ++)
            dp[i][j] = -0x3f3f3f3f;
    for (int i = 0; i < 27; i++) {
        if (s[3] == 'G' && cal(i) <= 0) continue;
        if (s[3] == 'R' && cal(i) >= 0) continue;
        if (s[3] == 'B' && cal(i) != 0) continue;
        dp[3][i] = (i % 3 == 0) + (i / 3 % 3 == 0) + (i / 9 % 3 == 0); 
    }
    for (int i =4; i<= n; i ++) {
    	for (int j = 0; j < 27; j ++) {
    		if (s[i] == 'G' && cal(j) <= 0) continue;
	        if (s[i] == 'R' && cal(j) >= 0) continue;
	        if (s[i] == 'B' && cal(j) != 0) continue;
    		for (int k = 0;  k < 27; k ++) {
    			if (j / 3 % 3 == k % 3 && k / 3 % 3 == j / 9 % 3)
    			dp[i][j] = max (dp[i][j], dp[i - 1][k] + (j % 3 == 0));
			}
		}
	}
	int maxv = -0x3f3f3f3f;
	for (int i = 0; i <= 26;i ++)
		maxv = max (maxv, dp[n][i]);
    if (maxv < 0) maxv = -1;
	cout << maxv << endl;
    return 0;
}

dp[i][state]表示前i个并且i, i - 1, i - 2对应的状态是state的最大的绿岛数量