/* -*- 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(0); break; case 'U': as.push_back(1); break; case 'R': as.push_back(2); break; case 'O': as.push_back(3); break; case 'I': as.push_back(4); break; case '?': as.push_back(-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, -1, sizeof(dp)); dp[0][0][0][0][0] = 0; int cur = 0, nxt = 1; for (int i = 0; i < n; i++) { int &ai = as[i]; for (int k = 0; k <= m; k++) for (int u = 0; u <= m; u++) for (int r = 0; r <= m; r++) for (int o = 0; o <= m; o++) { int &dpc = dp[cur][k][u][r][o]; if (dpc >= 0) { if (ai < 0) { int k0 = min(m, k + 1); if (dp[nxt][k0][u][r][o] < dpc) dp[nxt][k0][u][r][o] = dpc; int u0 = min(k, u + 1); if (dp[nxt][k][u0][r][o] < dpc) dp[nxt][k][u0][r][o] = dpc; int r0 = min(u, r + 1); if (dp[nxt][k][u][r0][o] < dpc) dp[nxt][k][u][r0][o] = dpc; int o0 = min(r, o + 1); if (dp[nxt][k][u][r][o0] < dpc) dp[nxt][k][u][r][o0] = dpc; 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; } } else if (ai == 0) { int k0 = min(m, k + 1); if (dp[nxt][k0][u][r][o] < dpc) dp[nxt][k0][u][r][o] = dpc; } else if (ai == 1) { int u0 = min(k, u + 1); if (dp[nxt][k][u0][r][o] < dpc) dp[nxt][k][u0][r][o] = dpc; } else if (ai == 2) { int r0 = min(u, r + 1); if (dp[nxt][k][u][r0][o] < dpc) dp[nxt][k][u][r0][o] = dpc; } else if (ai == 3) { int o0 = min(r, o + 1); if (dp[nxt][k][u][r][o0] < dpc) dp[nxt][k][u][r][o0] = dpc; } else if (ai == 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 <= m; u++) for (int r = 0; r <= m; r++) for (int o = 0; o <= m; o++) if (maxd < dp[cur][k][u][r][o]) maxd = dp[cur][k][u][r][o]; printf("%d\n", maxd); return 0; }