| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 164122 | toonewbie | Miners (IOI07_miners) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
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;
}
}