记录编号	32884	评测结果	AAAAAAAAAA
题目名称	机房	最终得分	100
用户昵称	lizhe	是否通过	通过
代码语言	Pascal	运行时间	0.165 s
提交时间	2011-11-08 19:26:01	内存使用	0.16 MiB

program orz;
const
  maxtin=1000000;
var
  i,j,n,m:longint;
  f,a,p1,p2:array[0..2500]of longint;
procedure init;
begin
  assign(input,'orz.in');
  reset(input);
  assign(output,'orz.out');
  rewrite(output);
  read(n,m);
  for i:=1 to n do
    read(a[i]);
  for i:=1 to n do
  begin
    p1[i]:=p1[i-1];
    p2[i]:=p2[i-1];
    if a[i]=1 then inc(p1[i])
    else inc(p2[i])
  end;
  for i:=1 to n do
    f[i]:=maxtin;
  f[1]:=1
end;

procedure dp;
begin
  for i:=1 to n do
    for j:=0 to i-1 do
      if (p1[i]-p1[j]=0) or (p2[i]-p2[j]=0) or (abs((p1[i]-p1[j])-(p2[i]-p2[j]))<=m) then
        if f[i]>f[j]+1 then
          f[i]:=f[j]+1
end;

procedure print;
begin
  writeln(f[n]);
  close(input);
  close(output)
end;

begin
  init;
  dp;
  print
end.