Untitled
unknown
c_cpp
a month ago
1.9 kB
4
Indexable
Never
#include<bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; #ifdef ONLINE_JUDGE #define debug(x...) #define testcase(tc) #else #include "../debug.h" #endif #define int long long int #define tp3(T) tuple<T,T,T> #define all(v) (v).begin(),(v).end() #define allr(v) (v).rbegin(),(v).rend() #define pr(x) cout << x << endl #define yesno(x) cout << ((x) ? "YES\n" : "NO\n") const int N =200200, MOD = 1000000009, INF = 1e15; template <class T> bool ckmin(T &a, const T &b) {return b < a ? a = b, 1 : 0;} template <class T> bool ckmax(T &a, const T &b) {return b > a ? a = b, 1 : 0;} typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset; typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset; // PRS int n; string s; vector<vector<int>> dp(N + 2, vector<int> (3, -INF)); signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> s; if (s[0] == 'R') { dp[0][1] = 1; } else if (s[0] == 'P') { dp[0][2] = 1; } else if (s[0] == 'S') { dp[0][0] = 1; } for (int i = 1; i < n; ++i) { if (s[i] == 'R') { dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + 1; } else if (s[i] == 'P') { dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + 1; } else if (s[i] == 'S') { dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + 1; } dp[i][0] = max(dp[i][0], max(dp[i-1][1], dp[i-1][2])); dp[i][1] = max(dp[i][1], max(dp[i-1][0], dp[i-1][2])); dp[i][2] = max(dp[i][2], max(dp[i-1][0], dp[i-1][1])); } cout << max({dp[n-1][0], dp[n-1][1], dp[n-1][2]}); return 0; }
Leave a Comment