const
  maxn=500;
var
  n,k:integer;
  s:array[1..maxn]of byte;
  f:array[1..maxn,1..maxn]of integer;
procedure init;
var i,j:integer;
begin
{  assign(input,'in.in');reset(input);}
  readln(n,k);
  for i:=1 to n do readln(s[i]);
end;

function g(p1,p2:integer):integer;
var i,sum:integer;
begin
  sum:=0;
  for i:=p1 to p2 do if s[i]=1 then inc(sum);
  g:=(p2-p1+1-sum)*sum;
end;

procedure dp;
var i,j,mik,i2,t:integer;
begin
  for i:=1 to n do
    begin
      if i<k then mik:=i else mik:=k;
      for j:=1 to mik do
        begin
          f[i,j]:=maxint;
          if j=1 then f[i,j]:=g(1,i)
          else
            for i2:=1 to i-j+1 do
              begin
                t:=f[i-i2,j-1]+g(i-i2+1,i);
                if t<f[i,j] then f[i,j]:=t;
              end;
        end;
    end;
end;

{=============main==============}
begin
init;
dp;
writeln(f[n,k]);
end.

Can someone give me a hint on solving this problem in O(n) and/or O(n^2) time? please it's for a school project, here is my e-mail: ethereal_2005_0@yahoo.com

Test 1 is the same as sample input in a problem?

And another question: if there are only black horces or onle white horces then the answer is count of horces or 0?

PLESE HELP ME!

P.S. I know that i don't know English well... Sorry for a mistakes.

Please some one help me by giving test case 1.

I am waiting for it.

Thank you.

[deleted by moderator]

Edited by moderator 13.04.2004 07:47

I always get wrong answer.
Could anybody help me?
Here is my programme:

var n,k,c,d,f,g,h:word; t:text;
    a,b:array[0..500] of word; e:array[1..500,1..500] of word;
begin
  assign(t,''); reset(t);
  readln(t,n,k);
  a[0]:=0; b[0]:=0;
  for c:=1 to n do begin
    readln(t,d);
    if d=0 then begin
      a[c]:=a[c-1]+1; b[c]:=b[c-1];
    end else begin
      a[c]:=a[c-1]; b[c]:=b[c-1]+1;
    end;
  end;
  close(t);
  for c:=1 to n do for d:=1 to k do e[c,d]:=65535;
  for c:=1 to n do begin
    e[c,1]:=a[c]*b[c];
    for d:=1 to c-1 do begin
      h:=(a[c]-a[d])*(b[c]-b[d]);
      if d<k-1 then f:=d else f:=k-1;
      for g:=1 to f do
        if e[c,g+1]>e[d,g]+h then e[c,g+1]:=e[d,g]+h;
    end;
  end;
  writeln(e[n,k]);
end.

I always get wrong answer.
Could you help me?