[HOJ] 45 - Miners

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
char in[100005];
int s[100005];
int dp[2][4][4][4][4][4];
int is[5];
int check(int a,int b,int c){
    memset(is,0,sizeof(is));
    is[a]=is[b]=is[c]=1;
    int i,ans=0;
    for(i=0;i<3;i++)
        if(is[i])
            ans++;
    return ans;
}
int main(){
    int n,i,j,a,b,c,d,e;
    scanf("%d%s",&n,in);
    memset(dp,-1,sizeof(dp));
    for(i=0;i<n;i++){
        if(in[i]=='M') s[i]=0;
        if(in[i]=='B') s[i]=1;
        if(in[i]=='F') s[i]=2;
    }
    int x=3;
    dp[1][x][x][x][x][x]=0;
    for(i=0;i<n;i++){
        memset(dp[0],-1,sizeof(dp[0]));
        for(a=0;a<4;a++)
        for(b=0;b<4;b++)
        for(c=0;c<4;c++)
        for(d=0;d<4;d++)
        for(e=0;e<4;e++){
            if(dp[1][a][b][c][d][e]!=-1){
                int u=check(s[i],x,a);
                dp[0][x][a][c][d][e]=max(dp[0][x][a][c][d][e],dp[1][a][b][c][d][e]+u);
                u=check(s[i],c,d);
                dp[0][c][d][x][a][b]=max(dp[0][c][d][x][a][b],dp[1][a][b][c][d][e]+u);
            }
        }
        memcpy(dp[1],dp[0],sizeof(dp[0]));
        x=s[i];
    }
    int ans=-132;
    for(a=0;a<3;a++)
    for(b=0;b<3;b++)
    for(c=0;c<3;c++)
    for(d=0;d<3;d++)
    for(e=0;e<3;e++)
        ans=max(ans,dp[1][a][b][c][d][e]);
    printf("%d\n",ans);
}