题解 P2782 【友好城市】

taoyc · 2017-10-14 16:36:20 · 题解

//疑似小学组题目？太水 lis+快排
//高手如云 lis在白书上有
type jl=record
  x,y:longint;
end;
var
  n,m,i,j,max:longint;
  a:array[1..100000] of jl;
  f:array[0..100000] of longint;
procedure sort(l,r: longint);
var
  i,j:longint;
  x,y:jl;
begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i].x<x.x do
            inc(i);
           while x.x<a[j].x do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
end;
begin
  readln(n);
  for i:=1 to n do
  begin
    readln(a[i].x,a[i].y);
    f[i]:=1;
  end;
  sort(1,n);
  max:=1;
 for i:=1 to n do
  begin
     for j:=1 to i-1 do
       if (a[j].y<a[i].y) and (f[j]+1>f[i]) then//lis
       begin
         f[i]:=f[j]+1;
         if f[i]>max then
           max:=f[i];
       end;
  end;
  writeln(max);//最大值打印
end.