记录编号	31774	评测结果	AAAAAAAAAAA
题目名称	[USACO Feb08] 麻烦的聚餐	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2011-11-03 20:17:38	内存使用	0.32 MiB

#include <fstream>
#include <climits>

#define I_F "egroup.in"
#define O_F "egroup.out"

const int MAXn=30000;

int n;
short s[MAXn];
int ans;

void Input();
inline int Min(const int, const int);
inline int Min(const int, const int, const int, const int, const int, const int);
void Dynap();
void Output();

int main()
{
	Input();
	Dynap();
	Output();
	return 0;
}

void Input()
{
	std::ifstream fin(I_F);
	fin>>n;
	for (int i=0; i<n; fin>>s[i++]);
	fin.close();
}

inline int Min(const int a, const int b)
{
	return (a<b)?a:b;
}

inline int Min(const int a, const int b, const int c, const int d, const int e, const int f)
{
	return Min(Min(a,Min(b,c)),Min(d,Min(e,f)));
}

void Dynap()
{
	int d1[4][MAXn]={{0}}, d2[4][MAXn]={{0}};
	for (short i=1; i<4; i++)
		for (int j=0; j<n; j++)
			d1[i][j]=d2[i][j]=INT_MAX;
	d1[1][0]=d1[2][0]=d1[3][0]=d2[1][0]=d2[2][0]=d2[3][0]=1;
	d1[s[0]][0]=d2[s[0]][0]=0;
	
	for (int i=1; i<n; i++)
	{
		for (short j=1; j<4; j++)
			for (short k=j; k>0; k--)
				d1[j][i]=Min(d1[j][i],(s[i]==j)?d1[k][i-1]:(d1[k][i-1]+1));
		for (short j=3; j>0; j--)
			for (short k=j; k<4; k++)
				d2[j][i]=Min(d2[j][i],(s[i]==j)?d2[k][i-1]:(d2[k][i-1]+1));
	}
	ans=Min(d1[1][n-1],d2[1][n-1],d1[2][n-1],d2[2][n-1],d1[3][n-1],d2[3][n-1]);
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<ans<<std::endl;
	fout.close();
}