#include #include #include #include #include #include #include #include #include #include #include #include #include #include constexpr int MAX_INT = 2147483647; constexpr int MIN_INT = -2147483648; #define rep(n, a, b) for (int (n) = (a); (n) < (b); (n)++) #define rrep(n, a, b) for (int (n) = (a); (n) >= (b); (n)--) #define llrep(n, a, b) for (long long (n) = (a); (n) < (b); (n)++) #define llrrep(n, a, b) for (long long (n) = (a); (n) >= (b); (n)--) #define itrAll(x) (x).begin(), (x).end() #define inputvec(v) for (auto& x : v) {std::cin >> x;} using namespace std; using uint = unsigned int; using ushort = unsigned short; using byte = unsigned char; using ll = long long; using ull = unsigned long long; using ldouble = long double; using ipair = pair; using llpair = pair; int main() { int N; string S; cin >> N >> S; vector cpc; // { 開始インデックス, 繰り返し回数 } rep(i, 0, N - 2) { if (S[i] == 'C') { int r_cnt = 0; for (int j = i + 1; j < N - 1; j += 2) { if (S[j] == 'P' && S[j + 1] == 'C') { r_cnt++; } else { break; } } if (r_cnt) { cpc.push_back({ i, r_cnt }); i += (r_cnt << 1); } } } if (!cpc.size()) { cout << 0 << endl; return 0; } /// /// [i] := { /// [first]: i+1番目のCPC...PCまでの部分文字列のうち, 少なくともi番目の「最後の」CPCを変換したときのCPCTFの個数の最大値. /// [second]: 〃のうち, i番目のCPCを変換していないときの〃. /// } /// vector cnt(cpc.size()); cnt[0] = { 0,0 }; for (int i = 1; i < cpc.size(); i++) { auto& prev = cpc[i - 1]; auto& current = cpc[i]; ipair prevIdx = { prev.first, prev.first + (prev.second << 1) }, currentIdx = { current.first, current.first + (current.second << 1) }; int margin = currentIdx.first - prevIdx.second - 1; if (margin == 1 && S[currentIdx.first - 1] == 'T') { // [..CPC]T[CPC..] if (current.second <= 2) { cnt[i] = { cnt[i - 1].second + 1, max(cnt[i - 1].first, cnt[i - 1].second) }; } else { int v = max(cnt[i - 1].first, cnt[i - 1].second + 1); cnt[i] = { v,v }; } } else if (margin >= 2 && S[prevIdx.second + 1] == 'T' && S[prevIdx.second + 2] == 'F') { // [..CPC]TF..[CPC..] int v = max(cnt[i - 1].first, cnt[i - 1].second + 1); cnt[i] = { v,v }; } else { // [..CPC][CPC..] or [..CPC]..[CPC..] int v = max(cnt[i - 1].first, cnt[i - 1].second); cnt[i] = { v,v }; } } auto& lastCpc = *(cpc.end() - 1); ipair lastIdx = { lastCpc.first, lastCpc.first + (lastCpc.second << 1) }; auto& c = *(cnt.end() - 1); if (lastIdx.second + 2 < N && S[lastIdx.second + 1] == 'T' && S[lastIdx.second + 2] == 'F') { cout << max(c.first, c.second + 1) << endl; } else { cout << max(c.first, c.second) << endl; } return 0; }