题意:在一个矩形区域内,机器人从左上角出发,每次只能沿着现在位置的下方和右方移动,在移动过程中收拾垃圾,一直到区域的右下角,现在给出所有垃圾的位置,
求解最少需要多少个机器人才能将这些垃圾清理成功.
解法:对于位置(x1,y1)和位置(x1,y2)处的垃圾,如果满足x1<=x2&&y1<=y2(当然不可能出现两个相同的坐标),那么这两个位置处的垃圾只需要一个机器人就可以成功
处理,则有Dilworth定理可知,将x坐标升序排序,相等时将y坐标升序排序(实际上题目就是按照这种形式输入),然后对y序列求解最长递减子序列数目即为所求。
贪心算法可求。同1065。
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
源代码
1
#include<iostream>
2
#include<algorithm>
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
using namespace std;
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
const int MAXN = 580;
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
struct Garbage
9![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
10
int r;
11
int c;
12
bool visited;
13
};
14![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
15
Garbage gar[MAXN];
16![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
17
bool com(Garbage s1, Garbage s2) //比较函数
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
19
if(s1.r == s2.r)
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
21
return s1.c < s2.c;
22
}
23
else
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
25
return s1.r < s2.r;
26
}
27
}
28![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
29
int main()
30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
31
int minR;
32
Garbage cur;
33
bool allVisited;
34
int ind; //当前序列的第一元素数组下标
35
int n;
36![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
37
cin>>gar[0].r>>gar[0].c;
38
while(!(gar[0].r == -1 && gar[0].c == -1))
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
40
gar[0].visited = false;
41
n = 0;
42
while(!(gar[n].r == 0 && gar[n].c == 0))
43![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
44
++n;
45
cin>>gar[n].r>>gar[n].c;
46
gar[n].visited = false;
47
}
48
++n;
49![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
50
sort(gar,gar+n,com); //排序
51![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
52
minR = 0;
53
ind = 0;
54
allVisited = false;
55
while(!allVisited)
56![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
57
allVisited = true;
58
for(;ind<n; ind++) //新序列
59![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
60
if(!gar[ind].visited)
61![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
62
cur = gar[ind];
63
gar[ind].visited = true;
64
allVisited = false;
65
++minR;
66
break;
67
}
68
}
69
for(int j=ind+1; j<n; j++)
70![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
71
if(!gar[j].visited && cur.r <= gar[j].r && cur.c <= gar[j].c)
72![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
73
cur = gar[j];
74
gar[j].visited = true;
75
}
76
}
77
}
78
cout<<minR<<endl;
79
cin>>gar[0].r>>gar[0].c;
80
}
81
return 0;
82
}