题解 P2782 【友好城市】

飞翔 · 2016-08-01 23:04:06 · 题解

先按照左边的城市排序，即消除动规的后效性。然后就是求右边的城市的最长不下降子序列了。

uses math;
var
  i,j,n,ans,maxx:longint;
    a,b,f:array[0..5001]of longint;
procedure qsort(l,r:longint);
var
  i,j,temp,mid:longint;
begin
  i:=l; j:=r;
  mid:=a[(l+r) div 2];
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
    begin
      temp:=a[i];a[i]:=a[j];a[j]:=temp;
      temp:=b[i];b[i]:=b[j];b[j]:=temp;
      inc(i);dec(j);
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
end;
begin
  readln(n);
    for i:=1 to n do readln(a[i],b[i]);
    qsort(1,n);
    f[1]:=1;
    ans:=1;
    for i:=2 to n do begin
      maxx:=0;
      for j:=i-1 downto 1 do
          if b[j]<b[i] then maxx:=max(maxx,f[j]);
        f[i]:=maxx+1;
      ans:=max(ans,f[i]);
    end;
    write(ans);
end.