记录编号	32932	评测结果	AAAAAAAAAA
题目名称	机房	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.337 s
提交时间	2011-11-08 20:03:58	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define min(a,b) ((a)<=(b)?(a):(b))
using namespace std;
int n,m,w[2510];
int q[2510],a[2510][2]={{0}};
bool check(int x,int y);
int main()
{
	freopen ("orz.in","r",stdin);
	freopen ("orz.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&w[i]);
		if (w[i]==1)
		{
			a[i][0]=a[i-1][0]+1;
			a[i][1]=a[i-1][1];
		}
		else
		{
			a[i][1]=a[i-1][1]+1;
			a[i][0]=a[i-1][0];
		}
	}
	for (int i=1;i<=n;i++)
	{
		q[i]=100000000;
	}
	for (int i=1;i<=n;i++)
	{
		for (int k=0;k<i;k++)
		{
			int d,e;
			d=abs((double)a[i][0]-a[k][0]);
			e=abs((double)a[i][1]-a[k][1]);
			if (d==0||e==0||(abs((double)d-e)<=m))
			{
				q[i]=min(q[i],q[k]+1);
			}
		}
	}
	cout<<q[n];
	return 0;
}