嘘解法かも。
まず考察する。
とにかく2パターンの使い方ができるIが面倒。
仮に、IOIが爆破されたら(使用できるのがJOIだけだったら)ハジから貪欲にほいほいつくればいい。
なので、文字列中のIを何文字かJに変換し、貪欲に取るという事を考える。
Iの何文字かの選び方が2^n通りなので、O(n2^n)で解ける。
だが、すべてのIの選び方について考えなくても、左側から何文字かIを選ぶという選び方だけ考えれば良い。
最適解において、(3文字目としてつかうI)が(1文字目としてつかうI)より左側に来ることがないようにできるから。(そのようなIのペアがあったらswapすればいい)
だからその何文字かを全パターン試せばおしまい。
#include <iostream> #include <vector> #include <cassert> #include <algorithm> #include <cstdio> #include <tuple> #include <cstring> using namespace std; typedef long long ll; typedef pair<int, int> P; const int MN = 1100100; int d[MN][2]; int r[MN][3]; int main() { int n; string s; cin >> n >> s; d[0][0] = d[0][1] = 0; for (int i = 0; i < n; i++) { d[i+1][0] = d[i][0]; d[i+1][1] = d[i][1]; if (s[i] == 'J' || s[i] == 'I') { d[i+1][0]++; } else { if (d[i+1][0]) { d[i+1][0]--; d[i+1][1]++; } } } r[n][0] = r[n][1] = r[n][2] = 0; for (int i = n-1; i >= 0; i--) { r[i][0] = r[i+1][0]; r[i][1] = r[i+1][1]; r[i][2] = r[i+1][2]; if (s[i] == 'J') { if (r[i][1]) { r[i][1]--; r[i][2]++; } } else if (s[i] == 'O') { if (r[i][0]) { r[i][0]--; r[i][1]++; } } else { r[i][0]++; } } for (int i = 0; i <= n; i++) { // printf("d %d 1:%d 2:%d\n", i, d[i][0], d[i][1]); } for (int i = 0; i <= n; i++) { // printf("r %d 1:%d 2:%d 3:%d\n", i, r[i][0], r[i][1], r[i][2]); } int res = 0; for (int i = 0; i <= n; i++) { int u = r[i][2]; int w = min(d[i][0], r[i][1]); u += w; d[i][0] -= w; r[i][1] -= w; w = min(d[i][1], r[i][0]); u += w; d[i][1] -= w; r[i][0] -= w; u += min(d[i][1], r[i][1]); res = max(res, u); //printf("%d %d\n", i, u); } cout << res << endl; return 0; }