#include <bits/stdc++.h>
#define endl '\n'
#define INF 2000000000
#define fi first
#define se second
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
pair<bool,int> dp[N][4][4][4][4];
int cmp(int a, int b, int c) {
if(c == a && c == b) return 1;
else if(c != a && c != b && a != b) return 3;
else return 2;
}
int main()
{
ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
int n; cin >> n; string s; cin >> s; int arr[n+1];
for(int i = 0; i < s.size(); i++) {
if(s[i] == 'M') arr[i+1] = 1;
else if(s[i] == 'F') arr[i+1] = 2;
else arr[i+1] = 3;
}
dp[0][0][0][0][0].fi = 1;
for(int i = 1; i <= n; i++) {
int sol = 0;
for(int j = 0; j < 4; j++) {
for(int z = 0; z < 4; z++) {
for(int q = 0; q < 4; q++) {
for(int w = 0; w < 4; w++) {
if(dp[i-1][j][z][q][w].fi == 1) {
if(z == 0) {
dp[i][0][arr[i]][q][w].fi = 1;
dp[i][0][arr[i]][q][w].se = max(dp[i][0][arr[i]][q][w].se,dp[i-1][j][z][q][w].se+1);
}
else if(j == 0) {
if(z == arr[i]) {
dp[i][z][arr[i]][q][w].fi = 1;
dp[i][z][arr[i]][q][w].se = max(dp[i][z][arr[i]][q][w].se,dp[i-1][j][z][q][w].se+1);
}
else {
dp[i][z][arr[i]][q][w].fi = 1;
dp[i][z][arr[i]][q][w].se = max(dp[i][z][arr[i]][q][w].se,dp[i-1][j][z][q][w].se+2);
}
}
else {
int where = cmp(j,z,arr[i]);
dp[i][z][arr[i]][q][w].fi = 1;
dp[i][z][arr[i]][q][w].se = max(dp[i][z][arr[i]][q][w].se,dp[i-1][j][z][q][w].se+where);
}
if(w == 0) {
dp[i][j][z][0][arr[i]].fi = 1;
dp[i][j][z][0][arr[i]].se = max(dp[i][j][z][0][arr[i]].se,dp[i-1][j][z][q][w].se+1);
}
else if(q == 0) {
if(w == arr[i]) {
dp[i][j][z][w][arr[i]].fi = 1;
dp[i][j][z][w][arr[i]].se = max(dp[i][j][z][w][arr[i]].se,dp[i-1][j][z][q][w].se+1);
}
else {
dp[i][j][z][w][arr[i]].fi = 1;
dp[i][j][z][w][arr[i]].se = max(dp[i][j][z][w][arr[i]].se,dp[i-1][j][z][q][w].se+2);
}
}
else {
int where = cmp(q,w,arr[i]);
dp[i][j][z][w][arr[i]].fi = 1;
dp[i][j][z][w][arr[i]].se = max(dp[i][j][z][w][arr[i]].se,dp[i-1][j][z][q][w].se+where);
}
}
}
}
}
}
}
int ans = 0;
for(int j = 0; j < 4; j++) {
for(int z = 0; z < 4; z++) {
for(int q = 0; q < 4; q++) {
for(int w = 0; w < 4; w++) {
if(dp[n][j][z][q][w].fi == 1) {
ans = max(ans,dp[n][j][z][q][w].se);
}
}
}
}
}
cout << ans << endl;
return 0;
}
Compilation message
miners.cpp: In function 'int main()':
miners.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
miners.cpp:26:13: warning: unused variable 'sol' [-Wunused-variable]
26 | int sol = 0;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
2396 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
10844 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
20572 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
50512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
69 ms |
151124 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
93 ms |
201300 KB |
Output is correct |
