이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1e5 + 5 ;
int n, dp[maxn][4][4][4][4], v[maxn] ;
string s ;
int solve(int i, int t11, int t12, int t21, int t22){ // os ultimos 2 importam qd add o novo
if(i >= n) return 0 ;
if(dp[i][t11][t12][t21][t22] != -1) return dp[i][t11][t12][t21][t22] ;
set<int> ans1, ans2 ;
if(t11 != 0) ans1.insert(t11) ;
if(t12 != 0) ans1.insert(t12) ;
//qto ganha ao add na mina 1 ou na 2 (qts diferentes tiver)
ans1.insert(v[i]) ;
ans2.insert(v[i]) ;
if(t21 != 0) ans2.insert(t21) ;
if(t22 != 0) ans2.insert(t22) ;
return dp[i][t11][t12][t21][t22] = max(ans1.size() + solve(i+1, v[i], t11, t21, t22), ans2.size() + solve(i+1, t11, t12, v[i], t21)) ;
//mlr colocar o atual em 1 ou 2?
}
int main(){
cin >> n ;
cin >> s ;
memset(dp, -1, sizeof dp) ;
for(int i = 0 ; i < n ; i++){
if(s[i] == 'M') v[i] = 1 ;
else if(s[i] == 'B') v[i] = 2 ;
else v[i] = 3 ;
}
cout << solve(0, 0, 0, 0, 0) << "\n" ;
}
# | 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... |