记录编号	32977	评测结果	AAAAAAAAAA
题目名称	机房	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.083 s
提交时间	2011-11-08 21:19:57	内存使用	0.29 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int M;
const int MAXN=2501;
int S1[MAXN];
int S2[MAXN];
int F[MAXN];

void init()
{
	S1[0]=0;
	S2[0]=0;
	scanf("%d %d\n",&N,&M);
	int tmp;
	for (int i=1;i<=N;i++)
	{
		scanf("%d\n",&tmp);
		if(tmp==1)
		{
			S1[i]=S1[i-1]+1;
			S2[i]=S2[i-1];
			continue;
		}
		if(tmp==2)
		{
			S1[i]=S1[i-1];
			S2[i]=S2[i-1]+1;
			continue;
		}
	}
}

int abs(int a)
{
	return a>=0?a:-a;
}

int Min(int a,int b)
{
	return a>b?b:a;
}

void dynamic()
{
	F[0]=0;
	F[1]=1;
	
	for (int i=2;i<=N;i++)
		F[i]=0x7fffffff;
	
	for (int i=2;i<=N;i++)
	{
		for (int j=1;j<=i;j++)
		{
			if( abs( (S1[i]-S1[j-1])-(S2[i]-S2[j-1]) )<=M || S1[i]-S1[j-1]==0 || S2[i]-S2[j-1]==0 )
				F[i]=Min(F[i],F[j-1]+1);
		}
	}
	printf("%d\n",F[N]);
}

int main()
{
	freopen("orz.in","r",stdin);
	freopen("orz.out","w",stdout);
	init();
	dynamic();
	return 0;
}