이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <char, int>
const int N = 2e4 + 5;
int dp[4][4][4][4], n, new_dp[4][4][4][4];
int jog = 0;
string s;
int jogap (int x, int y, int z) {
int ret = 0;
vector <int> v(4, 0);
v[x] = 1;v[y] = 1;v[z] = 1;
ret = v[1] + v[2] + v[3];
return ret;
}
void solve (int idx) {
if (idx == n + 1) return;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int l = 0; l < 4; ++l) {
for (int r = 0; r < 4; ++r) {
new_dp[i][j][l][r] = -1e9;
}
}
}
}
int val = 0;
if (s[idx] == 'F') val = 1;
else if (s[idx] == 'M') val = 2;
else val = 3;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int l = 0; l < 4; ++l) {
for (int r = 0; r < 4; ++r) {
new_dp[j][val][l][r] = max (new_dp[j][val][l][r], dp[i][j][l][r] + jogap (i, j, val));
new_dp[i][j][r][val] = max (new_dp[i][j][r][val], dp[i][j][l][r] + jogap (l, r, val));
}
}
}
}
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int l = 0; l < 4; ++l) {
for (int r = 0; r < 4; ++r) {
dp[i][j][l][r] = new_dp[i][j][l][r];
}
}
}
}
solve (idx + 1);
}
int main () {
// freopen ("input.txt", "r", stdin);
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> s;
s = " " + s;
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int l = 0; l < 4; ++l) {
for (int r = 0; r < 4; ++r) {
dp[i][j][l][r] = -1e9;
}
}
}
}
dp[0][0][0][0] = 0;
solve(1);
for (int i = 0; i < 4; ++i) {
for (int j = 0; j < 4; ++j) {
for (int l = 0; l < 4; ++l) {
for (int r = 0; r < 4; ++r) {
jog = max (dp[i][j][l][r], jog);
}
}
}
}
cout << jog;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |