比赛 20111102 评测结果 AAAAWAWWWWA
题目名称 麻烦的聚餐 最终得分 54
用户昵称 donny 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-02 19:22:55
显示代码纯文本
#include <iostream>
#include <fstream>

using namespace std;

int i,j,k,l,n;
int a[30010],f[30010][5];

int min(int x,int y)
{
	if (x>y)
		return y;
	return x;
}

int main()
{
	ifstream fin("egroup.in");
	ofstream fout("egroup.out");
	
	fin>>n;
	for (i=1;i<=n;i++)
		fin>>a[i];
	
	f[1][1]=f[1][2]=f[1][3]=1;
	if (a[1]==1)
		f[1][1]=0;
	else
	if (a[1]==2)
		f[1][2]=0;
	else
	if (a[1]==3)
		f[1][3]=0;
	
	for (i=2;i<=n;i++)
	{
		f[i][1]=f[i-1][1];
		if (a[i]!=1)
			f[i][1]++;
		f[i][2]=min(f[i-1][1],f[i-1][2]);
		if (a[i]!=2)
			f[i][2]++;
		f[i][3]=min(min(f[i-1][1],f[i-1][2]),f[i-1][3]);
		if (a[i]!=3)
			f[i][3]++;
	}
	k=min(min(f[n][1],f[n][2]),f[n][3]);
	
	f[1][1]=f[1][2]=f[1][3]=1;
	if (a[1]==1)
		f[1][1]=0;
	else
	if (a[1]==2)
		f[1][2]=0;
	else
	if (a[1]==3)
		f[1][3]=0;
	
	for (i=2;i<=n;i++)
	{
		f[i][3]=f[i-1][3];
		if (a[i]!=3)
			f[i][3]++;
		f[i][2]=min(f[i-1][1],f[i-1][2]);
		if (a[i]!=2)
			f[i][2]++;
		f[i][1]=min(min(f[i-1][1],f[i-1][2]),f[i-1][3]);
		if (a[i]!=1)
			f[i][1]++;
	}
	l=min(min(f[n][1],f[n][2]),f[n][3]);
	
	if (l<k)
		fout<<l<<endl;
	else
		fout<<k<<endl;
	
	fin.close();
	fout.close();
	return 0;
}