冒险公社,md

冒险公社,md

#includeusing 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的最大的绿岛数量

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。