首页 > 代码库 > 【POJ1548】Robots Dilworth定理（偏序集定理2）

【POJ1548】Robots Dilworth定理（偏序集定理2）

2024-07-31 07:21:11   218人阅读

题意：

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

题解：

    一看就是网络流经典题，或者说是二分图—最小路径覆盖；但是现在毕竟是在做一些贪心，这道题用的是一种贪心相关定理，Dilworth定理。

    这道题可以理解为部分两点之间有偏序（可走的关系），呃，可以视为当xa<=xb&&ya<=yb时有偏序，那么姑且认为反之则为反偏序，那么定义一条链为由n-1个偏序连接起来的n个点，那么答案就是“最长反链的大小。
    比如题中的数据1，我们经过处理得到2 4 4 6 4 7 6（排序去掉一维），然后就转化成了求最长下降子序列。

    显然逆序对是不能互相到达的，而反链就是一个逆序链，即我们所求的最长下降子序列。

    算是说了个大概，下面是偏序集的两个定理：

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


先贴代码题解再贴偏序相关。

模板是http://blog.csdn.net/error/404.html?from=http%3a%2f%2fblog.csdn.net%2fvmurder%2farticle%2fdetails%2f40818831

呃，图方便写了一发O（n^2）的算法，结果一直在写O（nlogn），然后（n^2）忘了，各种WA。。。我再也不写O（n^2）的lis了！！！

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 6000
#define inf 0x3f3f3f3f
using namespace std;
struct KSD
{
	int x,y;
	bool operator < (const KSD &a)const
	{if(x==a.x)return y<a.y;return x<a.x;}
}s[N];
int n,m,f[N];
int main()
{
//	freopen("test.in","r",stdin);
	int i,j,k;
	int x,y;
	s[0].y=inf;
	while(scanf("%d%d",&x,&y),x+1&&y+1)
	{
		int cnt=0;
		while(x&&y){s[++cnt].x=x,s[cnt].y=y,scanf("%d%d",&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);
			}
		}
		int ans=0;
		for(i=1;i<=cnt;i++)ans=max(ans,f[i]);
		printf("%d\n",ans);
	}
	return 0;
}





偏序关系

偏序存在A<B，A<C,则B与C之间无法比较大小的现象。而对应的全序则必须是形如A<B<C的形式。即全序要求每个元素之间都能比较大小，偏序不要求。

目录

1简介

2举例解释:

1简介

形式定义：
设R是集合A上的一个二元关系，若R满足：
Ⅰ 自反性：对任意x∈A，有xRx；
Ⅱ 反对称性：对任意x,y∈A，若xRy，且yRx，则x=y；
Ⅲ 传递性：对任意x, y,z∈A，若xRy，且yRz，则xRz。
则称R为A上的偏序关系，通常记作?。注意这里的?不必是指一般意义上的“小于或等于”。
若然有x?y，我们也说x排在y前面（x precedes y）。

2举例解释:

对于上述提到的自反性和传递性的举例解释:
集合A={a,b,c...}上的关系R是自反 指的是R有(a,a),(b,b),(c,c)...
R是传递，指若有(a,b)和(b,c), 则必有(a,c).
偏序（Partial Order）的概念：
设A是一个非空集，P是A上的一个关系，若P满足下列条件：
Ⅰ 对任意的a∈A，（a,a）∈P;(自反性 reflexlve）
Ⅱ 若（a,b）∈P，且（b,a）∈P，则 a=b;（反对称性，anti-symmentric）
Ⅲ 若（a,b）∈P，（b,c）∈P，则（a,c）∈P;（传递性，transitive）
则称P是A上的一个偏序关系。
若P是A上的一个偏序关系，我们用a≤b来表示（a,b）∈P。
整除关系便是一个定义在自然数上的一个偏序关系|，3|6的含义是3整除6。大于或等于也是定义在自然数集上的一个偏序关系。

偏序集

中文名
偏序集
记    作
≦
（自反性）
对任一，则x≦x;
（反对称性）
如果x≦y,且y≦x,则x=y;
设R为非空集合A上的关系，如果R是自反的、反对称的和传递的，则称R为A上的偏序关系，简称偏序，通常记作≦。
一个集合A与A上的偏序关系R一起叫作偏序集，记作<A,R>或<A, ≦>。
（自反性）对任一
，则x≦x;
（反对称性）如果x≦y,且y≦x,则x=y;
（传递性）如果x≦y,且y≦c ,则x≦c.


【POJ1548】Robots Dilworth定理（偏序集定理2）


联系
我们