| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 164122 | toonewbie | Miners (IOI07_miners) | Java | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
import java.util.*;
import java.io.*;
public class miners {
public static void main(String[] args) throws IOException{
BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new PrintStream(System.out));
n=Integer.parseInt(f.readLine());
char[]atem=f.readLine().toCharArray();
arr=new int[n];
for(int i=0;i<n;i++){
if(atem[i]=='M'){
arr[i]=1;
}
else if(atem[i]=='F'){
arr[i]=2;
}
else{
arr[i]=3;
}
}
int dp[][][][][][]=new int[n][4][4][4][4][2];
dp[0][0][0][0][0][0]=0;
dp[0][0][0][0][0][1]=0;
dp[1][0][arr[0]][0][0][0]=1+(arr[0]==arr[1]?1:2);
dp[1][0][arr[0]][0][0][1]=2;
dp[1][0][0][0][arr[0]][0]=2;
dp[1][0][0][0][arr[0]][1]=1+(arr[0]==arr[1]?1:2);
for(int i=1;i<n-1;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int p=0;p<4;p++){
for(int d=0;d<4;d++){
for(int u=0;u<2;u++){
if(dp[i][j][k][p][d][u]!=0){
int a=dp[i+1][j][k][d][arr[i]][1];
int b=dp[i+1][k][arr[i]][p][d][0];
if(u==0){
dp[i+1][k][arr[i]][p][d][0]=Math.max(b,dp[i][j][k][p][d][u]+numEqual(k,arr[i],arr[i+1]));
dp[i+1][k][arr[i]][p][d][1]=Math.max(b,dp[i][j][k][p][d][u]+numEqual(p,d,arr[i+1]));
}
if(u==1){
dp[i+1][j][k][d][arr[i]][1]=Math.max(a,dp[i][j][k][p][d][u]+numEqual(d,arr[i],arr[i+1]));
dp[i+1][j][k][d][arr[i]][0]=Math.max(a,dp[i][j][k][p][d][u]+numEqual(j,k,arr[i+1]));
}
}
}
}
}
}
}
}
int ans=0;
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int p=0;p<4;p++){
for(int d=0;d<4;d++){
for(int u=0;u<2;u++){
if(dp[n-1][j][k][p][d][u]>ans){
j=j;
}
ans=Math.max(ans,dp[n-1][j][k][p][d][u]);
}
}
}
}
}
System.out.print(ans);
f.close();
out.close();
}
static int numEqual(int a, int b, int c){
if(a==0 && b==0 && c==0)return 0;
if(a==0 && b==0)return 1;
if(a==0){
return b==c?1:2;
}
if(a==b && b==c)
return 1;
if(a==b)
return 2;
if(b==c)
return 2;
if(a==c)return 2;
return 3;
}
}
class pair implements Comparable <pair>{
int num;
int idx;
public int compareTo(pair other){
return num- other.num;
}
pair(int a, int b)
{
num=a;
idx=b;
}
}