记录编号	457894	评测结果	AAAAAAAAAA
题目名称	机房	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2017-10-09 20:13:30	内存使用	0.35 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
	return x*f;
}
const int maxn=2510;
int n,m;
int f[maxn];
int data[maxn],cnt1[maxn],cnt2[maxn];
inline int ok(int p){
	int fan=0,maxx=0x7fffffff;
	for(int i=1;i<=p;i++){
		int sum1=cnt1[p]-cnt1[i-1];
		int sum2=cnt2[p]-cnt2[i-1];
		if(abs(sum1-sum2)<=m||!sum1||!sum2){
			if(f[i-1]<maxx)
				maxx=f[i-1],fan=p-i+1;
		}
	}
	return fan;
}
int main(){
	freopen("orz.in","r",stdin);
	freopen("orz.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++)data[i]=read();
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){
		cnt1[i]=cnt1[i-1];
		cnt2[i]=cnt2[i-1];
		if(data[i]==1)cnt1[i]++;
		else cnt2[i]++;
	}
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]+1;//一个人一个机房； 
		int len=ok(i);
		f[i]=min(f[i],f[i-len]+1);
	}
	printf("%d\n",f[n]);
	return 0;
}