이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int INF=1e18;
//dp[i][a][b][c][d] ith position, a,b first mine c,d second mine
int to_int(char c){
if(c=='M')return 1;
if(c=='F')return 2;
return 3;
}
inline void solve(){
int n;cin>>n;
string s;cin>>s;
s=' '+s;
int dp[n+1][4][4][4][4]={0};
int ans=0;
int freq[4];
freq[1]=freq[2]=freq[3]=0;
freq[0]=INF;
freq[to_int(s[1])]++;
for(int i=1;i<=n;i++){
//freq[to_int(s[i])]++;
for(int a=0;a<4;a++){
for(int b=0;b<4;b++){
for(int c=0;c<4;c++){
//dp[i][s[i][a][b][c]
for(int d=0;d<4;d++){
dp[i][a][b][c][d]=-INF;
//cout<<"dp["<<i<<"]["<<a<<"]["<<b<<"]["<<c<<"]["<<d<<"]->"<<dp[i][a][b][c][d]<<"\n";
//ans=max(ans,dp[n][a][b][c][d]);
}
}
}
}
}
dp[1][to_int(s[1])][0][0][0]=1;
dp[1][0][0][to_int(s[1])][0]=1;
for(int i=2;i<=n;i++){
freq[to_int(s[i])]++;
for(int a=0;a<4;a++){
for(int b=0;b<4;b++){
for(int c=0;c<4;c++){
//dp[i][s[i][a][b][c]
for(int d=0;d<4;d++){
if(a==0&&d!=0)continue;
if(b==0&&c!=0)continue;
// 1 1 2 2
//
--freq[a];
--freq[b];
--freq[c];
--freq[d];
if(freq[a]<0||freq[b]<0||freq[c]<0||freq[d]<0){
++freq[a];
++freq[b];
++freq[c];
++freq[d];
continue;
}
++freq[a];
++freq[b];
++freq[c];
++freq[d];
set<int> ss;
for(int x:{to_int(s[i]),a,d}){
if(x!=0)ss.insert(x);
}
dp[i][to_int(s[i])][a][b][c]=
max(dp[i-1][a][d][b][c]+(int)ss.size(),
dp[i][to_int(s[i])][a][b][c]);
dp[i][b][c][to_int(s[i])][a]=
max(dp[i-1][b][c][a][d]+(int)ss.size(),dp[i][b][c][to_int(s[i])][a]);
//ans=max(ans,dp[i][b][c][to_int(s[i])][a]);
//ans=max(ans,dp[i][to_int(s[i])][a][b][c]);
}
}
}
}
}
//for(int i=1;i<=n;i++){
//freq[to_int(s[i])]++;
for(int a=0;a<4;a++){
for(int b=0;b<4;b++){
for(int c=0;c<4;c++){
//dp[i][s[i][a][b][c]
for(int d=0;d<4;d++){
//cout<<"dp["<<i<<"]["<<a<<"]["<<b<<"]["<<c<<"]["<<d<<"]->"<<dp[i][a][b][c][d]<<"\n";
ans=max(ans,dp[n][a][b][c][d]);
}
}
}
}
//}
cout<<ans;
}
signed main() {
cin.tie(NULL)->sync_with_stdio(false);
cout.tie(NULL);
solve();
}
# | 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... |