记录编号	532416	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[IOI 2007] 矿工配餐	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	2.303 s
提交时间	2019-05-29 14:06:28	内存使用	14.14 MiB

#include<bits/stdc++.h>
using namespace std; 
const int N=1e5+7; 
int v[N],dp[2][4][4][4][4],n,now;
char s[N];
int val(int x,int y,int z)
{
    if(!x && !y) return 1;
    if(!x) return 1+(y!=z);
    if(x==y && y==z) return 1;
    return(x!=y)+(y!=z)+(x!=z);
}
int main()
{
	freopen("miners.in","r",stdin);
	freopen("miners.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",s+1);
	for (int i=1;i<=n;i++)
	{
		if (s[i]=='M') v[i]=1;
		else if (s[i]=='F') v[i]=2;
		else if (s[i]=='B') v[i]=3;
	}
	memset(dp,-1,sizeof(dp)); dp[0][0][0][0][0]=0; 
	for (int i=1;i<=n;i++)
	{
		int k=v[i];
		now=i%2;
		for (int a=0;a<=3;a++)
		 for (int a1=0;a1<=3;a1++)
		  for (int b=0;b<=3;b++)
		   for (int b1=0;b1<=3;b1++)
		{
			if (dp[now^1][a][a1][b][b1]==-1) continue; 
			dp[now][k][a][b][b1]=max(dp[now][k][a][b][b1],dp[now^1][a][a1][b][b1]+val(a1,a,k));
			dp[now][a][a1][k][b]=max(dp[now][a][a1][k][b],dp[now^1][a][a1][b][b1]+val(b1,b,k)); 
		} 
	}
	int ans=0;
	for (int a=0;a<=3;a++)
	  for (int a1=0;a1<=3;a1++)
	   for (int b=0;b<=3;b++)
	     for (int b1=0;b1<=3;b1++) 
	ans=max(ans,dp[now][a][a1][b][b1]);
	printf("%d",ans); 
	return 0; 
}