3359: [Usaco2004 Jan]矩形

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 8  Solved: 5

[][][]

Description

    给出N个矩形(1≤N≤100)和它的长和宽(不超过1000)，写一个程序找出最大的K，使得

有K个矩形满足层层包含的关系，即里层的矩形被所有外层的矩形包含．一个矩形P1包含另一个

矩形P2，则P2的一边小于P1的一边，并且P9的另一边不超过P1的另一边．如果两个矩形相同，视为不包含．如2 x 1的矩形被2x2的矩形包含，不被1 x 2的矩形包含．

    注意：矩形的顺序可以是任意的，且矩形可以旋转．

Input

    第1行：整数N．

    第2到N+1行：矩形的长和宽，均为整数．

Output

    一行，输出最大的包含数K.

Sample Input

4

8 14

16 28

29 12

14 8

Sample Output

2

HINT

 

Source

 

题解：其实很明显有更好的办法的，但是我还是逗比的建立了一个拓扑图（A-->B表示A举行包含在B里面，为了方便，我还弄了个 \( -1 * -1 \) 的矩形作为源点），然后去用spfa求出从源点出发各个点的最长路径，然后求出最大值即可

1 type 2         point=^node; 3         node=record 4                 g,w:longint; 5                 next:point; 6         end; 7 var 8         i,j,k,l,m,n,f,r:longint; 9         p:point;10         a:array[0..10000,1..2] of longint;11         b:array[0..10000] of point;12         c,g:array[0..10000] of longint;13         d:array[0..100000] of longint;14 procedure add(x,y,z:longint);inline;15         var p:point;16         begin17                 new(p);p^.g:=y;p^.w:=z;18                 p^.next:=b[x];b[x]:=p;19         end;20 procedure swap(var x,y:longint);inline;21         var z:longint;22         begin23                 z:=x;x:=y;y:=z;24         end;25 procedure sort(l,r:longint);inline;26         var i,j,x,y:longint;27         begin28                 i:=l;j:=r;x:=a[(l+r) div 2,1];y:=a[(l+r) div 2,2];29                 repeat30                         while (a[i,1]
      
       x) or ((a[j,1]=x) and (a[j,2]>y)) do dec(j);32                         if i<=j then33                                 begin34                                         swap(a[i,1],a[j,1]);35                                         swap(a[i,2],a[j,2]);36                                         inc(i);dec(j);37                                 end;38                 until i>j;39                 if i
       
        a[i,2] then swap(a[i,1],a[i,2]);48                 end;49         a[n+1,1]:=-1;a[n+1,2]:=-1;n:=n+1;50         sort(1,n);51         for i:=1 to n do b[i]:=nil;52         for i:=1 to n-1 do53                 for j:=i+1 to n do54                         if (a[j,2]>a[i,2]) or ((a[j,2]>=a[i,2]) and (a[j,1]>a[i,1])) then55                                 begin56                                         add(i,j,1);57                                 end;58         f:=1;r:=2;d[1]:=1;g[1]:=1;59         fillchar(c,sizeof(c),0);60         while f
        
         nil do64                                 begin65                                         if (c[d[f]]+p^.w)>c[p^.g] then66                                                 begin67                                                         c[p^.g]:=p^.w+c[d[f]];68                                                         if g[p^.g]=0 then69                                                                 begin70                                                                         g[p^.g]:=1;71                                                                         d[r]:=p^.g;72                                                                         inc(r);73                                                                 end;74                                                 end;75                                         p:=p^.next;76                                 end;77                         g[d[f]]:=0;78                         inc(f);79                 end;80         l:=0;81         for i:=1 to n do if c[i]>l then l:=c[i];82         writeln(l);83 end.