首页 > 代码库 > Dilworth定理
Dilworth定理
这个定理和一个对偶定理,讲的意思大概就是,给一个偏序关系,比如说是一个数它出现的位置i在另一个数出现的位置j之前,而且满足ai>aj.那么满足这个偏序关系的链就叫做链.关于链和反链:
链（chain）是一个偏序集S的全序子集（所谓全序是指任意两个元素可比较）
反链（antichain）是一个偏序集S的子集，其中任意两个元素不可比较.
dilworth说的是:最大链的长度等于最少反链覆盖数.而最大反链的长度等于最少链覆盖数.
看下这个定理的一个应用.
Hdu1257导弹拦截系统,以前有个经典的dp题是求最长不升子序列的,那就是求满足偏序关系i<j且ai>=aj的最长链的长度.根据dilworth,它应该等于最少反链覆盖数.也就是用贪心求出所有上升的序列,然后统计个数,这就是最少反链覆盖数.
而这个题是求需要的最少的导弹拦截系统的数量,其实就是求反链个数.也就是求最长链的长度,所以贪心求个数可以解,求dp也可以解.
1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <math.h> 5 #include <stdlib.h> 6 using namespace std; 7 #define maxn 100005 8 //dilworth定理的应用 定义偏序关系 x<=y <=为{i<j时,hi>=hj} 即最少链覆盖数 应该等于 最长反链数即求最大的满足偏序关系 {i<j时 hi<hj}的链长度 9 //所以该问题就是求最长上升子序列10 //普通方法是O(n^2) 二分是O(nlgm)11 int h[maxn],f[maxn];12 int main()13 {14 int n,i,j,k;15 while(~scanf("%d",&n))16 {17 for(i=1;i<=n;i++)18 scanf("%d",&h[i]);19 f[1]=1;20 int res=1;21 for(i=2;i<=n;i++)22 {23 int temp=0;24 for(j=1;j<i;j++)25 if(h[i]>h[j])26 if(temp<f[j]) temp=f[j];27 f[i]=temp+1;28 if(f[i]>res) res=f[i];29 }30 cout<<res<<endl;31 }32 return 0;33 }
Dilworth定理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。