Untitled

mail@pastecode.io avatar
unknown
c_cpp
5 months ago
1.9 kB
4
Indexable
#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