记录编号	72915	评测结果	AAAAAAAAAA
题目名称	机房	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.141 s
提交时间	2013-10-19 18:05:01	内存使用	0.25 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int SIZEN=2501;
const int INF=0x7fffffff;
int n,m;
int afan[SIZEN]={0},bfan[SIZEN]={0};//甲乙二人的崇拜者个数前缀和
int dfan[SIZEN]={0};//甲乙二人的崇拜者人数之差前缀和(甲-乙)
void init(void){
	int i,x;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		if(x==1){//甲
			afan[i]=afan[i-1]+1;
			bfan[i]=bfan[i-1];
		}
		else{
			afan[i]=afan[i-1];
			bfan[i]=bfan[i-1]+1;
		}
		dfan[i]=afan[i]-bfan[i];
	}
}
int sdv(int x,int y){
	int ans;
	ans=dfan[y]-dfan[x-1];
	return abs(ans);
}
bool able(int x,int y){
	if(sdv(x,y)<=m) return true;
	if(afan[y]-afan[x-1]==0) return true;
	if(bfan[y]-bfan[x-1]==0) return true;
	return false;
}
int f[SIZEN]={0};
void work(void){
	//隐含:f[0]=0
	int i,j;
	for(i=1;i<=n;i++) f[i]=INF;
	for(i=1;i<=n;i++){
		for(j=0;j<i;j++){//尝试将j+1到i的诸人分到一个机房
			if(able(j+1,i)){
				f[i]=min(f[i],f[j]+1);
			}
		}
	}
}
int main(){
	freopen("orz.in","r",stdin);
	freopen("orz.out","w",stdout);
	init();
	work();
	printf("%d\n",f[n]);
	return 0;
}