Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- int n;
- string s;
- int ans;
- int cal[9999][4][4][4][4];
- bool caltrue[9999][4][4][4][4];// initialized as false
- bool bb[4];
- int score(int a=1, int b=1, int c=2) {
- memset(bb, false, sizeof(bb));
- bb[a] = true;
- bb[b] = true;
- bb[c] = true;
- int res = 0;
- for (int i = 1; i <= 3; ++i) res += bb[i];
- return res;
- // return __builtin_popcount(((1 << a) | (1 << b) | (1 << c)) >> 1);
- }
- int dp(int f, char a, char b, char c, char d){
- if (f >= n) return 0;
- if(caltrue[f][a][b][c][d]) return cal[f][a][b][c][d];
- // if(score(a, b, s[f])>score(c, d, s[f])
- int x = dp(f + 1, s[f], a, c, d) + score(a, b, s[f]);
- int y = dp(f + 1, a, b, s[f], c) + score(c, d, s[f]);
- caltrue[f][a][b][c][d]=true;
- if (x > y){
- cal[f][a][b][c][d]=x;
- return x;
- }
- else {
- cal[f][a][b][c][d]=y;
- return y;
- }
- }
- int main() {
- cin >> n >>s;
- for (int i = 0; i < n; ++i) {
- if (s[i] == 'M') s[i] = 1;
- if (s[i] == 'F') s[i] = 2;
- if (s[i] == 'B') s[i] = 3;
- }
- for (int f = n - 1; f >= 0; --f) {
- for (int a = 0; a <= 3; ++a) {
- for (int b = 0; b <= 3; ++b) {
- for (int c = 0; c <= 3; ++c) {
- for (int d = 0; d <= 3; ++d) {
- int x = cal[(f + 1) % 2][s[f]][a][c][d] + score(a, b, s[f]);
- int y = cal[(f + 1) % 2][a][b][s[f]][c] + score(c, d, s[f]);
- cal[f % 2][a][b][c][d] = max(x, y);
- /* int x = dp(f + 1, s[f], a, c, d) + score(a, b, s[f]);
- int y = dp(f + 1, a, b, s[f], c) + score(c, d, s[f]); */
- }
- }
- }
- }
- }
- cout << cal[0][0][0][0][0];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement