Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <cstring>
- #include <set>
- using namespace std;
- const int maxn = 55000;
- const int INF = 2e9;
- string s;
- int n;
- int dp[maxn][4][4][4][4];
- int score(int a, int b, int c) {
- set<int> st;
- if(a != 4) {
- st.insert(a);
- }
- if(b != 4) {
- st.insert(b);
- }
- if(c != 4) {
- st.insert(c);
- }
- return (int) st.size();
- }
- int color(char c) {
- if(c == 'R') return 0;
- if(c == 'G') return 1;
- return 2;
- }
- int rec(int at, int L1, int L2, int R1, int R2) {
- if(at == n) {
- return 0;
- }
- if(dp[at][L1][L2][R1][R2] != -1) {
- return dp[at][L1][L2][R1][R2];
- }
- int res = -INF;
- int score_left = score(L1, L2, color(s[at]));
- res = max(res, rec(at + 1, L2, color(s[at]), R1, R2) + score_left);
- int score_right = score(R1, R2, color(s[at]));
- res = max(res, rec(at + 1, L1, L2, R2, color(s[at])) + score_right);
- dp[at][L1][L2][R1][R2] = res;
- return res;
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin >> n >> s;
- memset(dp, -1, sizeof dp);
- cout << rec(0, 4, 4, 4, 4) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment