/* -*- coding: utf-8 -*- * * 291.cc: No.291 黒い文字列 - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100; const int MAX_M = MAX_N / 5; /* typedef */ typedef vector vi; /* global variables */ vi as; int dp[2][MAX_M + 1][MAX_M + 1][MAX_M + 1][MAX_M + 1]; /* subroutines */ /* main */ int main() { string s; cin >> s; for (int i = 0; i < s.size(); i++) switch (s[i]) { case 'K': as.push_back(1 << 0); break; case 'U': as.push_back(1 << 1); break; case 'R': as.push_back(1 << 2); break; case 'O': as.push_back(1 << 3); break; case 'I': as.push_back(1 << 4); break; case '?': as.push_back((1 << 5) - 1); break; } int n = as.size(); int m = n / 5; //for (int i = 0; i < n; i++) printf("%d ", as[i]); putchar('\n'); memset(dp[0], -1, sizeof(dp[0])); dp[0][0][0][0][0] = 0; int cur = 0, nxt = 1; for (int i = 0; i < n; i++) { int &ai = as[i]; memcpy(dp[nxt], dp[cur], sizeof(dp[nxt])); for (int k = 0; k <= m; k++) for (int u = 0; u <= k; u++) for (int r = 0; r <= u; r++) for (int o = 0; o <= r; o++) { int &dpc = dp[cur][k][u][r][o]; if (dpc >= 0) { //printf("dp[%d][%d][%d][%d]=%d\n", k, u, r, o, dpc); if (ai & (1 << 0)) { int k0 = min(m, k + 1); if (dp[nxt][k0][u][r][o] < dpc) dp[nxt][k0][u][r][o] = dpc; } if (ai & (1 << 1)) { int u0 = min(k, u + 1); if (dp[nxt][k][u0][r][o] < dpc) dp[nxt][k][u0][r][o] = dpc; } if (ai & (1 << 2)) { int r0 = min(u, r + 1); if (dp[nxt][k][u][r0][o] < dpc) dp[nxt][k][u][r0][o] = dpc; } if (ai & (1 << 3)) { int o0 = min(r, o + 1); if (dp[nxt][k][u][r][o0] < dpc) dp[nxt][k][u][r][o0] = dpc; } if (ai & (1 << 4)) { if (k > 0 && u > 0 && r > 0 && o > 0) { int d0 = dpc + 1; if (dp[nxt][k - 1][u - 1][r - 1][o - 1] < d0) dp[nxt][k - 1][u - 1][r - 1][o - 1] = d0; } } } } cur ^= 1, nxt ^= 1; } int maxd = 0; for (int k = 0; k <= m; k++) for (int u = 0; u <= k; u++) for (int r = 0; r <= u; r++) for (int o = 0; o <= r; o++) if (maxd < dp[cur][k][u][r][o]) maxd = dp[cur][k][u][r][o]; printf("%d\n", maxd); return 0; }