Advertisement
giangvi

uva103-kei

Mar 13th, 2011
3,075
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. const
  2.         fi = 'uva103.inp';
  3.         fo = 'uva103.out';
  4.  
  5. type
  6.         box = array[1..10] of longint;
  7.         boxes = array[1..300] of box;
  8.  
  9.  
  10. var
  11.         f,g:text;
  12.         a:boxes;
  13.         fx,fa:array[1..300] of longint;
  14.         n,k,i,j:longint;
  15.  
  16. procedure sort(var a:box; k:longint);
  17. var
  18.         i,j,tmp:longint;
  19. begin
  20.         for i:=1 to k-1 do
  21.                 for j:=i+1 to k do
  22.                 if a[i]>a[j] then
  23.                 begin
  24.                         tmp:=a[i];
  25.                         a[i]:=a[j];
  26.                         a[j]:=tmp;
  27.                 end;
  28. end;
  29.  
  30. procedure swap(var x,y:box);
  31. var t:box;
  32. begin
  33.         t:=x;  x:=y; y:=t;
  34. end;
  35.  
  36. function cmp(x,y:box):boolean;
  37. var i:longint;
  38. begin
  39.         for i:=1 to n do
  40.         if x[i] > y[i] then exit(false);
  41.         exit(true);
  42. end;
  43.  
  44. procedure sort2(var a:boxes; k:longint);
  45. var
  46.         i,j:longint;
  47. begin
  48.         for i:=1 to k-1 do
  49.                 for j:=i+1 to k do
  50.                         if cmp(a[j],a[i]) then swap(a[i],a[j]);
  51. end;
  52.  
  53. procedure dynprog;
  54. var
  55.         i,j,max:longint;
  56. begin
  57.         sort2(a,k);
  58.         fillchar(fx,sizeof(fx),0);
  59.         fx[1]:=1;
  60.         max:=0;
  61.         for i:=2 to k do
  62.         begin
  63.                 for j:=1 to i-1 do
  64.                         if (cmp(a[j],a[i])) and (fx[i] < fx[j]+1) then
  65.                         begin
  66.                                 fx[i]:=fx[j]+1;
  67.                                 fa[j]:=i;
  68.                         end;
  69.                 if max<fx[i] then max:=fx[i];
  70.         end;
  71.         writeln(g,max);
  72. end;
  73.  
  74. begin
  75.         assign(f,fi); reset(f);
  76.         assign(g,fo); rewrite(g);
  77.         while not seekeof(f) do
  78.         begin
  79.                 readln(f,k,n);
  80.                 for i:=1 to k do
  81.                 begin
  82.                         for j:=1 to n do read(f,a[i,j]);
  83.                         sort(a[i],n);
  84.                         readln(f);
  85.                 end;
  86.                 dynprog;
  87.         end;
  88.         close(f); close(g);
  89. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement