记录编号	453594	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	愉快的logo设计	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	1.293 s
提交时间	2017-09-21 20:25:26	内存使用	71.81 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
#define Sum(l,r,t) (sum[r][t]-sum[l-1][t])
using namespace std;
const int maxn=1500000;
int k,ans=maxn,a[12]={1,4,16,64,256,1024,4096,16384,65536,262144,1048576};
char s[maxn*2];
int sum[maxn*2][3],f[maxn*2][3];
int main(){
	freopen("JOI.in","r",stdin);
	freopen("JOI.out","w",stdout);
	scanf("%d%s",&k,s+1);
	for(int i=1;i<=a[k];i++)s[i+a[k]]=s[i];
	for(int i=1;i<=a[k]*2;i++){
		if(s[i]=='J')sum[i][0]=sum[i-1][0]+1,sum[i][1]=sum[i-1][1],sum[i][2]=sum[i-1][2];
		if(s[i]=='O')sum[i][1]=sum[i-1][1]+1,sum[i][0]=sum[i-1][0],sum[i][2]=sum[i-1][2];
		if(s[i]=='I')sum[i][2]=sum[i-1][2]+1,sum[i][0]=sum[i-1][0],sum[i][1]=sum[i-1][1];
	}
	for(int j=1;j<=k;j++)
		for(int i=1;i+a[j]-1<=a[k]*2;i++)
			f[i][j]=Sum(i,i+a[j-1]-1,1)
			       +Sum(i,i+a[j-1]-1,2)
				   +Sum(i+a[j-1],i+a[j-1]*2-1,0)
				   +Sum(i+a[j-1],i+a[j-1]*2-1,2)
				   +Sum(i+a[j-1]*2,i+a[j-1]*3-1,0)
				   +Sum(i+a[j-1]*2,i+a[j-1]*3-1,1)
				   +f[i+a[j-1]*3][j-1];
	int ans=0x3f3f3f3f;
	for(int i=1;i<=a[k];i++)ans=min(ans,f[i][k]);
	printf("%d\n",ans);
	return 0;
}