记录编号	175097	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[IOI 2007] 矿工配餐	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	0.495 s
提交时间	2015-08-04 16:17:21	内存使用	0.41 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,ans;
char ch[100005];
int f[5][4][4][4][4];
inline int getint(char c)
{
	if(c=='M')return 1;
	else if(c=='F')return 2;
	else return 3;
}
inline int cal(int a,int b,int c)
{
	int tmp=1;
	if(a!=0&&a!=b&&a!=c)tmp++;
	if(b!=0&&b!=c)tmp++;
	return tmp;
}
int main()
{
	freopen("miners.in","r",stdin);
	freopen("miners.out","w",stdout);
	memset(f,-1,sizeof(f));
	f[0][0][0][0][0]=0;
	n=read();
	scanf("%s",ch);
	for(int i=0;i<n;i++)
	    for(int a1=0;a1<=3;a1++)
	        for(int a2=0;a2<=3;a2++)
	            for(int b1=0;b1<=3;b1++)
	                for(int b2=0;b2<=3;b2++)
	{
		int x=i%4,y=(i+1)%4;
		if(f[x][a1][a2][b1][b2]==-1)continue;
		int t=getint(ch[i]),tmp;
		tmp=cal(a1,a2,t);
		f[y][a2][t][b1][b2]=max(f[y][a2][t][b1][b2],f[x][a1][a2][b1][b2]+tmp);
		tmp=cal(b1,b2,t);
		f[y][a1][a2][b2][t]=max(f[y][a1][a2][b2][t],f[x][a1][a2][b1][b2]+tmp);
	}
	for(int a1=0;a1<=3;a1++)
	    for(int a2=0;a2<=3;a2++)
	        for(int b1=0;b1<=3;b1++)
	            for(int b2=0;b2<=3;b2++)
	                ans=max(ans,f[n%4][a1][a2][b1][b2]);
	printf("%d",ans);
	return 0;

}