题解 P2782 【友好城市】

scarborough_fair · 2016-10-29 18:46:48 · 题解

这道题算是比较裸的不下降序列，对两岸坐标进行排序然后dp一遍就行了。（感觉测试数据很弱，当年测评机不会只有三个点吧）

**var i,j,k,l,n,max1,ans:longint;
    a,b,f:array[0..10000] of longint;
function max(x,y:longint):longint;
begin if x>y then exit(x);exit(y);end;
procedure sort(l,r:longint);
var i,j,m,t:longint;
begin
  i:=l;j:=r;m:=a[(i+j)div 2];
  repeat
  while a[i]<m do inc(i);
  while a[j]>m do dec(j);
    if i<=j then
      begin
         t:=a[i];a[i]:=a[j];a[j]:=t;
         t:=b[i];b[i]:=b[j];b[j]:=t;
         inc(i);dec(J);
      end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;
begin
  //assign(input,'sihp.in');reset(input);
  //assign(output,'ship.out');rewrite(output);
  readln(n); f[1]:=1;ans:=1;
  for i:=1 to n do
    readln(a[i],b[i]);
  sort(1,n);
  for i:=2 to n do
    begin max1:=0; for j:=i-1 downto 1 do
      if b[j]<b[i] then max1:=max(max1,f[j]);
      f[i]:=max1+1;
      ans:=max(f[i],ans);
    end;        write(ans);
  //close(input);close(output);
end.
**