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

#define INF 0x7FFFFFFF
#define MAX 30001
 
using namespace std;
 
int f[MAX][4];
int s[MAX];
int n,ans=INF;
 
void init()
{
	int i;
	freopen("egroup.in","r",stdin);
	freopen("egroup.out","w",stdout);
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>s[i];
}
 
void dynamic()
{
	int i,j,k;
	for(j=1;j<=3;j++)
	{
		for(i=1;i<=n;i++)
		{
			f[i][j]=INF;
			for(k=1;k<=j;k++)
			{
				if(f[i-1][k]<f[i][j])
					f[i][j]=f[i-1][k];
			}
			if(s[i]!=j)
				f[i][j]++;
		}
		if(f[n][j]<ans)
			ans=f[n][j];
	}
	for(j=3;j>=1;j--)
	{
		for(i=1;i<=n;i++)
		{
			f[i][j]=INF;
			for(k=j;k<=3;k++)
			{
				if(f[i-1][k]<f[i][j])
					f[i][j]=f[i-1][k];
			}
			if(s[i]!=j)
				f[i][j]++;
		}
		if(f[n][j]<ans)
			ans=f[n][j];
	}
}
 
int main()
{
	init();
	dynamic();
	cout<<ans<<endl;
	return 0;
}