이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
Note :
Link :
Boka hoye gelum...
*/
#include "bits/stdc++.h"
#define sp <<" "
#define el <<"\n"
#define S second
#define F first
#define pb push_back
#define all(ar) ar.begin(),ar.end()
#define pii pair<ll,ll>
using namespace std;
using ll = long long;
using ld = long double;
const ll mod = 1000000007;
const ll oo = 3372036000000000;
const ll si = 100005;
int mao[si][4][4][4][4],n;
string s;
vector<int> man;
int point(int a,int b,int c){
int ans = 3;
if(a == 0 || b == 0){
if(a == 0) ans--;
if(b == 0) ans--;
return ans;
}
if(a == b && b == c) ans = 1;
else if(a == b) ans = 2;
else if(a == c) ans = 2;
else if(b == c) ans = 2;
return ans;
}
int dp(int i, int a1, int a2, int b1, int b2){
if(i == n) return 0;
if(mao[i][a1][a2][b1][b2] == -1){
int ans = 0, x = man[i];
ans = max(dp(i + 1, a2, x, b1, b2) + point(a1,a2,x), dp(i + 1, a1, a2, b2, x) + point(b1,b2,x));
mao[i][a1][a2][b1][b2] = ans;
}
return mao[i][a1][a2][b1][b2];
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
/*
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
//*/
cin>>n>>s;
man.resize(n);
int i = 0;
for(char r: s){
if(r == 'F') man[i++] = 1;
else man[i++] = (r == 'M' ? 2 : 3);
}
memset(mao,-1,sizeof(mao));
cout<<dp(0,0,0,0,0);
return 0;
}
/*
check for:
*missed a break, continue ?
*corner cases, n = 1?
*overflow.
*unnecessary logics.
*impreciseness caused by double or long double.
*/
# | 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... |