MCARDS - Card Sorting

Tác giả: RR

Ngôn ngữ: Pascal

//Written by Nguyen Thanh Trung
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       444;
type
  cards         =       record u,color,val:longint; end;
var
  f1,f2         :       text;
  best,n,k      :       longint;
  a             :       array[1..MAXN] of cards;
  d             :       array[1..MAXN] of longint;
  dd,pos        :       array[1..4] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i:longint;
    begin
      read(f1,k,n);
      for i:=1 to n*k do
        with a[i] do read(f1,color,u);
    end;
procedure solve;
    var
      i,j:longint;
    begin
      for i:=n*k downto 1 do
        with a[i] do val:=pos[color]*n+u;
      for i:=1 to n*k do
        begin
          d[i]:=1;
          for j:=i-1 downto 1 do
            if a[j].val<a[i].val then
              d[i]:=max(d[i],d[j]+1);
          best:=max(best,d[i]);
        end;
    end;
procedure dequy(i:longint);
    var
      j:longint;
    begin
      for j:=1 to k do
        if dd[j]=0 then
          begin
            dd[j]:=1; pos[j]:=i-1;
            if i<k then dequy(i+1)
            else solve;
            dd[j]:=0;
          end;
    end;

begin
  openF;
  inp;
  dequy(1);
  writeln(f2,n*k-best);
  closeF;
end.

Download