来自"NOCOW"

如果a包含b，则a向b连一条有向边，再用拓扑排序球最长路即可。

program cao;
const
  maxn=600;
 
var
  map:array[0..maxn,0..maxn] of boolean;
  v,d,fa,ans,x,y,queue:array[0..maxn*10] of longint;
  a,b,c,e,f,g,h,i,j,k,l,n,m,p,q,closed,open:longint;
 
procedure init;
begin
  read(n);
  for i:=1 to n do
    read(x[i],y[i]);
end;
 
procedure main;
begin
  for i:=1 to n do
    for j:=1 to n do
      if (x[j]<x[i])and(y[j]>y[i]) then
      begin
        inc(d[j]);
        map[i,j]:=true;
      end;
  closed:=1;
  for i:=1 to n do
    if d[i]=0 then
    begin
      inc(open);
      queue[open]:=i;
    end;
  repeat
    p:=queue[closed];
    for i:=1 to n do
      if map[p,i] then
      begin
        if v[p]+1>v[i] then
        begin
          v[i]:=v[p]+1;
          fa[i]:=p;
        end;
        dec(d[i]);
        if d[i]=0 then
        begin
          inc(open);
          queue[open]:=i;
        end;
      end;
    inc(closed);
  until closed>open;
end;
 
procedure print;
begin
  l:=-1;
  for i:=n downto 1 do
    if v[i]>l then
    begin
      l:=v[i];
      k:=i;
    end;
  writeln(l+1);
  l:=0;
  while k<>0 do
  begin
    inc(l);
    ans[l]:=k;
    k:=fa[k];
  end;
  for i:=l downto 1 do
    write(ans[i],‘ ‘);
  writeln;
end;
 
begin
  init;
  main;
  print;
end.

http://www.withflying.com/?p=140

http://www.withflying.com

---

直接按长度从大到小快排一遍 然后顺推 非常常规的算法。

program cyd;
  var
    s,le,ri,e,d,pre:array[1..500]of longint;
    i,j,k,l,m,n,a,b,c,ans:longint;
  procedure swap(var a,b:longint);
    var
      c:longint;
    begin
      c:=a;
      a:=b;
      b:=c;
    end;
  procedure qsort(l,r:longint);
    var
      tl,tr,mid,tmp:longint;
    begin
      tl:=l; tr:=r; mid:=e[(l+r)div 2];
      repeat
        while e[tl]>mid do inc(tl);
        while e[tr]<mid do dec(tr);
        if tl<=tr then
          begin
            swap(le[tl],le[tr]);
            swap(ri[tl],ri[tr]);
            swap(e[tl],e[tr]);
            swap(d[tl],d[tr]);
            inc(tl); dec(tr);
          end;
        until tl>tr;
      if tl<r then qsort(tl,r);
      if tr>l then qsort(l,tr);
    end;
  begin
    readln(n);
    for i:=1 to n do
      begin
        read(le[i],ri[i]);
        e[i]:=ri[i]-le[i];
        d[i]:=i;
      end;
    qsort(1,n);
    for i:=1 to n do
      begin
        for j:=i+1 to n do
          if (le[i]<le[j])and(ri[j]<ri[i])and(s[i]+1>s[j]) then
            begin
              s[j]:=s[i]+1;
              pre[j]:=i;
            end;
        if s[i]+1>ans then ans:=s[i]+1;
      end;
    for i:=n downto 1 do if s[i]+1=ans then break;
    j:=i;
    writeln(ans);
    while j<>0 do
      begin
        write(d[j],' ');
        j:=pre[j];
      end;
  end.