记录编号	33065	评测结果	AAAAAAAAAA
题目名称	机房	最终得分	100
用户昵称	Yeehok	是否通过	通过
代码语言	C	运行时间	0.085 s
提交时间	2011-11-09 14:11:14	内存使用	0.26 MiB

#include<stdio.h>
int n,m;
int num[2501]={0};
int f[2501]={0};
int absint(int x)
{
	return (x>0 ? x:-x);
}
int mn(int a,int b)
{
	return a<b ? a:b;
}
int main()
{
	FILE *f1=fopen("orz.in","r");
	FILE *f2=fopen("orz.out","w");
	fscanf(f1,"%d%d",&n,&m);
	int i,j;
	int tmp;
	for(i=1;i<=n;i++)
	{
		fscanf(f1,"%d",&tmp);
		num[i]=(tmp==2 ? 1:0);
	}
	int s1[2501],s2[2501];
	s1[1]=(num[1]==0 ? 1:0);
	s2[1]=(num[1]==1 ? 1:0);
	for(i=2;i<=n;i++)
	{
		s1[i]=s1[i-1]+(num[i]==0 ? 1:0);
		s2[i]=s2[i-1]+(num[i]==1 ? 1:0);
	}
	for(i=1;i<=n;i++)
	{
		f[i]=210000000;
		for(j=1;j<=i;j++)
		{
			if(s1[j-1]-s1[i]==0||s2[j-1]-s2[i]==0||absint(s1[j-1]-s1[i]-s2[j-1]+s2[i])<=m)
				f[i]=mn(f[i],f[j-1]+1);
		}
	}
	fprintf(f2,"%d\n",f[n]);
	fclose(f1);
	fclose(f2);
	return (0);
}