记录编号	306575	评测结果	AAAAAAAAAA
题目名称	机房	最终得分	100
用户昵称	kito	是否通过	通过
代码语言	C++	运行时间	0.083 s
提交时间	2016-09-12 17:12:15	内存使用	0.33 MiB

#include<cstdio>
#include<cstring>
using namespace std;
#define	fcl	fclose(stdin);	fclose(stdout);	return 0
int n,m;
int F[2510],T1[2510],T2[2510];
int A[2510]={0};

int ABS(int a){
	if(a<0)	return -a;
	return a;
}

int Get_Min(const int& a,const int& b){
	if(a<b)	return a;
	return b;
}

int GT1(int l,int r){
	return T1[r]-T1[l-1];
}

int GT2(int l,int r){
	return T2[r]-T2[l-1];
}

int main(){
	freopen("orz.in","r",stdin);
	freopen("orz.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	memset(F,0x3f,sizeof(F));
	for(int i=1;i<=n;++i){
		scanf("%d",&A[i]);
		T1[i]=T1[i-1];	T2[i]=T2[i-1];
		if(A[i]==1)	T1[i]++;
		else	T2[i]++;
	}
	//F[i]表示前i个人最少用多少个机房。
	//第i个人要么自己新开一个机房，要么和前面的人一起用一个机房。 
	F[0]=0;
	int x,y;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=i;++j){
			//枚举j，看看从j到i能否放入一个机房。 
			x=GT1(j,i);	y=GT2(j,i);
			if(x==0||y==0||ABS(x-y)<=m){
				F[i]=Get_Min(F[i],F[j-1]+1);
			}
		}
	}
	printf("%d",F[n]);
	fcl;
}