在一個(gè)網(wǎng)格中有某些垃圾，機(jī)器人只能向下或向右，當(dāng)某個(gè)機(jī)器人走到垃圾處時(shí)，看做它撿起了這個(gè)垃圾，現(xiàn)在給定各垃圾坐標(biāo)求撿起所有垃圾最少需要的機(jī)器人數(shù)。

很明顯的最小路徑覆蓋，但是再向深里挖呢？？

把坐標(biāo)按x升序排序，x相同保證y升序，那么某一個(gè)機(jī)器人撿起的垃圾組成的序列必是x，y的最長(zhǎng)不降序列，問題轉(zhuǎn)化為求用最少的不降序列覆蓋原序列

由偏序集的Dilworth定理，這個(gè)答案就是原序列的最長(zhǎng)下降序列，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.

轉(zhuǎn)載于:https://www.cnblogs.com/neverforget/archive/2012/02/29/2373846.html

總結(jié)

以上是生活随笔為你收集整理的pku1548 Robots的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。