出动最少的机器人收集硬币算法/机器人收硬币算法/完整代码+理论推理
题目如下：
本题要求出动最少的机器人来收集场上所有的硬币，首先容易想到的是设计算法使得机器人每次行动都尽可能收集数量最多的硬币，但是实际上此解法并不可行，如以下这种情况:
优先找数量最多的话那么应当是：
以上四种情况，但是实际应当是三种最少，因此优先金币最多是错误的，考虑新的思路。
注意到若两金币其中一个金币在另一个金币的右上方则必须出动两个机器人，如下:
因为机器人只能向右或向下移动，(2, 2)和(3, 3)的机器人是不可能用同一个机器人访问的，因此该特性为题目的突破口。 考虑一个 m×n 网格，机器人从左上角 (1,1) 开始，向右下角 (m,n) 结束
偏序关系定义
设网格的行号 i 从上到下增加（即 i=1 是顶行），列号 j 从左到右增加（即 j=1 是左列）。因此，左上角为 (1,1)，右下角为 (m,n)，令 S 为所有硬币点的集合。每个点 p∈S 有坐标 (i, j)。因此对于满足以上关系的点对p, q，其坐标满足ip <= iq 且 jp <= jq , 是一个偏序关系
偏序关系具有可比较性，如果两点p,q互相满足以上偏序关系，那么我们称这两点为可比较的，放在图中就是一个点在另一个点的右下或左上方（包括横向），而一点在另一点的右上方我们称其为不可比较的。进一步，硬币集合S就是定义在图上的偏序集。因此，一个机器人所访问的路线中任意两点必须可比。
链与反链的定义
【集合论】序关系 ( 链 | 反链 | 链与反链示例 | 链与反链定理 | 链与反链推论 | 良序关系 )
对于本题，集合S是偏序集，那么上文已经给出一个机器人所走的路线上的硬币必然两两可比，因此机器人走的路线就是这个集合S上的一条链。 因此我们所找的最小机器人数目就是这个集合上的最小链划分的数目。
进一步解释一下： 最小链划分中链的数指的是：对于一个给定的有限偏序集 S，在它的所有可能的链划分（chain partition）中，链的数量最少的那一个划分所包含的链的个数。
链划分（chain partition） 是将偏序集 S 划分成若干个互不相交的链（chain），使得每个元素属于恰好一个链（即，这些链覆盖了 S 的所有元素，且彼此不重叠）。
最小链划分（minimum chain partition）
是指这样的一个链划分，使得链的数量（即链的个数）最小化。也就是说，在所有可能的链划分中，它使用了最少数量的链。 因此，“最小链划分中链的数目”就是这个最小数量，即最小链划分中链的个数，也就是至少需要的机器人数目。 至于如何计算这个最小链划分中链的数目，有一个著名的定理：
狄尔沃斯（Dilworth）定理
狄尔沃斯（Dilworth）[百度百科] 狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理，是关于偏序集的极大极小的定理，该定理断言：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目，由偏序集P按如下方式产生的图G称为偏序集的可比图：G的节点集由P的元素组成，而e为G中的边，仅当e的两端点在P中是可比较的，有限全序集的可比图为完全图。 因此对于本题，我们只需要找到最大反链中元素数目即 最大的连续不可比的点的数目。
完整代码实现
图使用二维数组：
#include<bits/stdc++.h>
// 机器人收硬币
using namespace std;
vector<vector<int>> arr = {
{1, 0, 0, 1, 0, 0},
{0, 1, 1, 0, 1, 0},
{0, 1, 1, 0, 0, 0},
{0, 1, 1, 1, 0, 0},
{0, 1, 0, 1, 1, 0}
};
int max_num = 0;
int rows = arr.size(); // 网格的行数
int cols = arr[0].size(); // 网格的列数
对于如何找到最大反链，编者采用从第一列开始直到最后一列扫描所有反链来求解。
int findOne(int x, int y){
int i = x+1;
int num = 1;
// 下一列
while(i < cols){
int y_end = -1;
for(int j=0;j<rows;j++){
if(arr[j][i] == 1 && j < y){
y_end = j;
}
}
if(y_end == -1){
cout<<i<<"列没有找到"<<endl;
}else{
cout<<x<<","<<y<<"右上角的坐标已找到"<<i<<","<<y_end<<endl;
cout<<"连续斜线的点数量为"<<num+1<<"-------!"<<endl;
num++;
y = y_end;
}
// 下一列
i = i+1;
}
return num;
}
这个函数的作用是输入一个节点的坐标，能够计算出从这一列开始的不同组的金币数，我们还是举个例子：
比如从第二列的最后一个点开始(1, 4)，第三列的倒数第二个点是无法用同一个机器人访问的该列的最后一个点，然后算法会从这个点开始(2, 3)，再找出第四列的第一个点（无法用同一个机器人访问的该列的最后一个点）(3,0)，然后第五，六列就没有符合的点了，因此从第二列开始的最大不同组数为 3， 包含第二列能找到三个点，因此该反链长为3。 为什么从最后一个点开始 因为对于本题来说，一个不可比的点对就是满足一个点在另一个点的右上方，因此我们尽可能找最长反链当然要从最后一个点开始。
然后我们主函数内只需要用两个for循环分别找每列的最后一个点即可：
for(int i=0;i<cols;i++){
int y_end = -1;
for(int j=0;j<rows;j++){
if(arr[j][i] != 0){
y_end = j;
}
}
// 找到最后的y，进入函数
if(y_end != -1){
cout<<"----------找到了x:"<<i<<" y:"<<y_end<<"的最后一个点，进入循环------"<<endl;
int num = findOne(i, y_end);
if(num > max_num){
max_num = num;
}
}
}
以下是完整代码：
#include<bits/stdc++.h>
// 机器人收硬币
using namespace std;
vector<vector<int>> arr = {
{1, 0, 0, 1, 0, 0},
{0, 1, 1, 0, 1, 0},
{0, 1, 1, 0, 0, 0},
{0, 1, 1, 1, 0, 0},
{0, 1, 0, 1, 1, 0}
};
int max_num = 0;
int rows = arr.size(); // 网格的行数
int cols = arr[0].size(); // 网格的列数
int findOne(int x, int y){
int i = x+1;
int num = 1;
// 下一列
while(i < cols){
int y_end = -1;
for(int j=0;j<rows;j++){
if(arr[j][i] == 1 && j < y){
y_end = j;
}
}
if(y_end == -1){
cout<<i<<"列没有找到"<<endl;
}else{
cout<<x<<","<<y<<"右上角的坐标已找到"<<i<<","<<y_end<<endl;
cout<<"连续斜线的点数量为"<<num+1<<"-------!"<<endl;
num++;
y = y_end;
}
// 下一列
i = i+1;
}
return num;
}
int main(){
for(int i=0;i<cols;i++){
int y_end = -1;
for(int j=0;j<rows;j++){
if(arr[j][i] != 0){
y_end = j;
}
}
// 找到最后的y，进入函数
if(y_end != -1){
cout<<"----------找到了x:"<<i<<" y:"<<y_end<<"的最后一个点，进入循环------"<<endl;
int num = findOne(i, y_end);
if(num > max_num){
max_num = num;
}
}
}
cout<<"至少派出机器人数量为:"<<max_num;
return 0;
}
end