Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 8 Solved: 5
给出N个矩形(1≤N≤100)和它的长和宽(不超过1000),写一个程序找出最大的K,使得
有K个矩形满足层层包含的关系,即里层的矩形被所有外层的矩形包含.一个矩形P1包含另一个
矩形P2,则P2的一边小于P1的一边,并且P9的另一边不超过P1的另一边.如果两个矩形相同,视为不包含.如2 x 1的矩形被2x2的矩形包含,不被1 x 2的矩形包含.
注意:矩形的顺序可以是任意的,且矩形可以旋转.
第1行:整数N.
第2到N+1行:矩形的长和宽,均为整数.
一行,输出最大的包含数K.
4 8 14 16 28 29 12 14 8
2
题解:其实很明显有更好的办法的,但是我还是逗比的建立了一个拓扑图(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 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.