3359: [Usaco2004 Jan]矩形

 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         begin
17                 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         begin
23                 z:=x;x:=y;y:=z;
24         end;
25 procedure sort(l,r:longint);inline;
26         var i,j,x,y:longint;
27         begin
28                 i:=l;j:=r;x:=a[(l+r) div 2,1];y:=a[(l+r) div 2,2];
29                 repeat
30                         while (a[i,1]<x) or ((a[i,1]=x) and (a[i,2]<y)) do inc(i);
31                         while (a[j,1]>x) or ((a[j,1]=x) and (a[j,2]>y)) do dec(j);
32                         if i<=j then
33                                 begin
34                                         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<r then sort(i,r);
40                 if l<j then sort(l,j);
41         end;
42 begin
43         readln(n);
44         for i:=1 to n do
45                 begin
46                         readln(a[i,1],a[i,2]);
47                         if a[i,1]>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 do
53                 for j:=i+1 to n do
54                         if (a[j,2]>a[i,2]) or ((a[j,2]>=a[i,2]) and (a[j,1]>a[i,1])) then
55                                 begin
56                                         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<r do
61                 begin
62                         p:=b[d[f]];
63                         while p<>nil do
64                                 begin
65                                         if (c[d[f]]+p^.w)>c[p^.g] then
66                                                 begin
67                                                         c[p^.g]:=p^.w+c[d[f]];
68                                                         if g[p^.g]=0 then
69                                                                 begin
70                                                                         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.