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

#include<iostream>
#include<fstream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>

using namespace std;

const int oo=0x7fffffff;

int n,m,a[5001];
long long f[5001];

int main()
{
	int i,j,k;
	ifstream fin("orz.in");
	ofstream fout("orz.out");
	fin>>n>>m;
	for(i=1;i<=n;i++)
	{
		fin>>k;
		if(k==1)
			a[i]=a[i-1]-1;
		else
			a[i]=a[i-1]+1;
	}
	for(i=1;i<=n;i++)
		f[i]=oo;
	f[1]=1;
	for(i=2;i<=n;i++)
		for(j=0;j<i;j++)
			if(abs(a[i]-a[j])<=m||abs(a[i]-a[j])==i-j)
				f[i]=min(f[i],f[j]+1);
	fout<<f[n]<<endl;
	fin.close();
	fout.close();
	return 0;
}