在一个网格中有某些垃圾，机器人只能向下或向右，当某个机器人走到垃圾处时，看做它捡起了这个垃圾，现在给定各垃圾坐标求捡起所有垃圾最少需要的机器人数。
很明显的最小路径覆盖，但是再向深里挖呢？？
把坐标按x升序排序，x相同保证y升序，那么某一个机器人捡起的垃圾组成的序列必是x，y的最长不降序列，问题转化为求用最少的不降序列覆盖原序列
由偏序集的Dilworth定理，这个答案就是原序列的最长下降序列，n^2算法即可。
View Code
1 program pku1548(input,output);
2 var
3 f : array[0..1000] of longint;
4 x,y : array[0..1000] of longint;
5 n : longint;
6 procedure swap(var aa,bb: longint );
7 var
8 tt : longint;
9 begin
10 tt:=aa;
11 aa:=bb;
12 bb:=tt;
13 end; { swap }
14 procedure sort(p,q :longint );
15 var
16 i,j,m1,m2 : longint;
17 begin
18 i:=p;
19 j:=q;
20 m1:=x[(i+j)>>1];
21 m2:=y[(i+j)>>1];
22 repeat
23 while (x[i]<m1)or((x[i]=m1)and(y[i]<m2)) do
24 inc(i);
25 while (x[j]>m1)or((x[j]=m1)and(y[j]>m2)) do
26 dec(j);
27 if i<=j then
28 begin
29 swap(x[i],x[j]);
30 swap(y[i],y[j]);
31 inc(i);
32 dec(j);
33 end;
34 until i>j;
35 if i<q then sort(i,q);
36 if j>p then sort(p,j);
37 end; { sort }
38 function main():longint;
39 var
40 i,j : longint;
41 begin
42 main:=0;
43 fillchar(f,sizeof(f),0);
44 for i:=1 to n do
45 for j:=i-1 downto 1 do
46 if (y[i]<y[j]) then
47 if f[j]+1>f[i] then
48 begin
49 f[i]:=f[j]+1;
50 if f[i]>main then
51 main:=f[i];
52 end;
53 inc(main);
54 end; { main }
55 begin
56 readln(x[1],y[1]);
57 while (x[1]<>-1)and(y[1]<>-1) do
58 begin
59 n:=2;
60 readln(x[2],y[2]);
61 while x[n]+y[n]<>0 do
62 begin
63 inc(n);
64 readln(x[n],y[n]);
65 end;
66 sort(1,n);
67 writeln(main);
68 fillchar(x,sizeof(x),0);
69 fillchar(y,sizeof(y),0);
70 readln(x[1],y[1]);
71 end;
72 end.