记录编号	34203	评测结果	AAAAAAAAAA
题目名称	机房	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2011-12-03 21:42:24	内存使用	0.30 MiB

#include <fstream>
using namespace std;  
ifstream fin("orz.in");
ofstream fout("orz.out");
const long long Infinite=1000000000;
int N,M;  int S[2501],sum1[2501],sum2[2501],f[2501];
template <class T>
T Abs(T a)  
{  
    if (a<0)  
        return(0-a);  
    else  
        return(a);  
}  

void Init()
{
	fin>>N>>M;
	for(int i=1;i<=N;i++)
	{
		fin>>S[i];
		if(S[i]==1)
		{
			sum1[i]=sum1[i-1]+1;
			sum2[i]=sum2[i-1];
		}
		else
		{
			sum1[i]=sum1[i-1];
			sum2[i]=sum2[i-1]+1;
		}
	}
}
int main()  
{
	int i,j;
	Init();
	for(i=1;i<=N;i++)
	{
		int Min=Infinite;
		for(j=1;j<=i;j++)
		{
			int A1=sum1[i]-sum1[j-1],A2=sum2[i]-sum2[j-1];
			if(A2==0 || A1==0 || Abs(A2-A1)<=M)
			{
				if(Min>f[j-1]+1)
					Min=f[j-1]+1;
			}
		}
		f[i]=Min;
	}
	fout<<f[N]<<endl;
	fin.close();
	fout.close();
    return 0 ;
}  
/*if(A1==j-i+1 || A2==j-i+1 || Abs(A2-A1)<=M)*/