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

#include<fstream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
ifstream fi("orz.in");
ofstream fo("orz.out");
const int SIZE=2510;
int N,M,admire[2][SIZE],f[SIZE];
int main()
{
	memset(admire,0,sizeof(admire));
	int i,j;
	fi>>N>>M;
	admire[0][0]=0;admire[1][0]=0;
	for(i=1;i<=N;i++)
	{
		fi>>j;
		j--;
		admire[j][i]=admire[j][i-1]+1;
		admire[!j][i]=admire[!j][i-1];
	}
	for(i=1;i<=N;i++)
	{
		f[i]=i;
		if(abs(admire[1][i]-admire[0][i])<=M||admire[1][i]==0||admire[0][i]==0)
		{
			f[i]=1;
			continue;
		}
			for(j=1;j<=i-1;j++)
				if(admire[1][i]-admire[1][j]==0||admire[0][i]-admire[0][j]==0||abs((admire[1][i]-admire[1][j])-(admire[0][i]-admire[0][j]))<=M)
					f[i]=min(f[i],f[j]+1);
	}
	fo<<f[N]<<endl;
	return 0;
}