poj1548-Robots Dilworth定理（偏序集定理2）

储备知识：Dilworth定理

偏序集的两个定理：

定理1)

令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。 其对偶定理称为Dilworth定理：

定理2)

令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

即：链的最少划分数 = 反链的最长长度

例如：

1 7 8 2 3 4

反链：最长不上升子序列（如：（7，2））长度 = 2；

即：按升序划分，最少的链划分数为2，为（1，2，3，4）和（7，8）。

以上转自：https://www.cnblogs.com/submarinex/archive/2011/08/03/2126423.html

回到题目：Robot

题意：

有一些位置有垃圾，让机器人从左上角开始走，只能往右或者往下，问最少走多少次可以清理完所有垃圾、

题解：

一看就是网络流经典题，或者说是二分图—最小路径覆盖；但是现在毕竟是在做一些贪心，这道题用的是一种贪心相关定理，Dilworth定理。 这道题可以理解为部分两点之间有偏序（可走的关系），呃，可以视为当xa<=xb&&ya<=yb时有偏序，那么姑且认为反之则为反偏序，那么定义一条链为由n-1个偏序连接起来的n个点，那么答案就是“最长反链的大小。 比如题中的数据1，我们经过处理得到2 4 4 6 4 7 6**（排序去掉一维）**，然后就转化成了求最长下降子序列。 显然逆序对是不能互相到达的，而反链就是一个逆序链，即我们所求的最长下降子序列。

————————————————

原文链接：https://blog.csdn.net/Vmurder/article/details/40818033

//2018114766 2020/7/3 #include<iostream> #include<algorithm> using namespace std; #define MAX 1000 #define inf 0x3f3f3f3f struct point { int x, y; bool operator < (const point& a)const//重载<操作符。可以对两个point使用<操作符进行比较 { if (x == a.x)return y < a.y; return x < a.x; } }s[MAX]; int f[MAX]; int main() { int x, y,i,j; s[0].y = inf;//给[0]一个大值，使得单元素链的长度也能为1，否则在处理中为零 while (cin >> x >> y,x+1,y+1) {//读取case的第一个点 int cnt = 0; while (x && y) {//存储并读取这一个case s[++cnt].x = x; s[cnt].y = y;//！这里不用++，x、y是同一个元素下的 cin >> x >> y; } sort(s+1,s+cnt+1); //计算偏序集,找最长下降链的长度 for (i = 1; i <= cnt; i++) { f[i] = 0; for (j = i - 1; j >= 0; j--) { if (s[j].y > s[i].y) f[i] = max(f[i], f[j] + 1);//i在j结尾的最大链上+1 } } //找到最长反链 int ans = 0; for (i = 1; i <= cnt; i++) ans = max(ans, f[i]); cout << ans << endl; } }