이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, v[100001];
ll memo[100001][4][4][4][4];
int score(int a, int b, int c)
{
if (b == 3) b = c;
if (a == 3) a = b;
if (a == b && b == c) return 1;
if (a == b || b == c || c == a) return 2;
return 3;
}
ll dp(int i, int a = 3, int b = 3, int c = 3, int d = 3)
{
if (memo[i][a][b][c][d] != -1)
return memo[i][a][b][c][d];
if (i > N) return 0;
return memo[i][a][b][c][d] = max(dp(i + 1, b, v[i], c, d) + score(a, b, v[i]), dp(i + 1, a, b, d, v[i]) + score(c, d, v[i]));
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for (int i = 1; i <= N; i++)
{
char x;
cin >> x;
v[i] = (x == 'F') + 2 * (x == 'B');
}
for (int i = 0; i <= N; i++)
for (int a = 0; a < 4; a++)
for (int b = 0; b < 4; b++)
for (int c = 0; c < 4; c++)
for (int d = 0; d < 4; d++)
memo[i][a][b][c][d] = -1;
cout << dp(1) << '\n';
return 0;
}
# | 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... |