偏序定理 poj 3636 + poj 1065.doc

小记3小记4偏序集 Dilworth 定理 poj 1065 3636 1548 在Partially order set(偏序集)有一个非常NX的定理叫Dilworth Theorem。上图是偏序集的一个Hasse diagram，偏序集的定义是偏序是在集合X上的二元关系，它满足自反性、反对称性和传递性。即，对于X中的任意元素a,b和c，有:自反性：aa;反对称性：如果ab且ba，则有a=b;传递性：如果ab且bc，则ac 。带有偏序关系的集合称为偏序集。令(X,)是一个偏序集，对于集合中的两个元素a、b，如果有ab或者ba，则称a和b是可比的，否则a和b不可比。在X中，对于元素a，如果任意元素b，由ba得出b=a，则称a为极小元。一个反链A是X的一个子集，它的任意两个元素都不能进行比较。 一个链C是X的一个子集，它的任意两个元素都可比。下面是两个重要定理：定理1 令（X,）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。 其对偶定理称为Dilworth定理： 定理2 令（X,）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。搞清楚了反链和链的定义，就能够很好的从Hasse Diagram中得到理解。链就是从纵向的角度看 Hasse Diagram ,反链是从横向的角度看Hasse Diagram。定理一，就是至少有r行构成反链关系。定理二，就是至少有m列构成链关系。 我们来考虑一个导弹拦截问题，就是求一个序列的最长不上升子序列，以及求能最少划分成几组不上升子序列。 很显然第一个是动态规划，动态规划的过程就是求Hasse Diagram的过程！ 第二问就是求最少能够划分成几个链，根据定理2 ，很显然就是反链的最大长度。反链就是一个上升子序列。即求一个严格上升子序列的最大长度。 注意一个问题是，在获得偏序集有几个主链的时候，需要对数据集先进行排序，然后从头开始，沿着主链顺序DFS。由于导弹拦截的问题，天然有序，形成了严格上升自序列，所以没有凸显这个问题！ POJ 1065 注意一个比较诡异的是algorithm 中的sort,会出现一个断言错误！。不太清楚什么情况。其他照做就OK#include #include #include using namespace std;struct Stick int l; int w;int cmp(Stick a,Stick b) if(a.l=b.l ) return (a.w b.w); else return (a.l T; for(int t=1;tn; vector S(n); for(int i=0;iSi.lSi.w; int dp6005; memset(dp,0,sizeof(dp); sort(S.begin(),S.end(),cmp); for(int i=0;in;i+) if(dpi=0) dpi=1; Stick cut=Si; for(int j=i+1;jn;j+) if( dpj=0 & (cut.l=Sj.l & cut.w=Sj.w ) ) dpj=-1; cut=Sj; int res=0; for(int i=0;in;i+) res+=dpi=1?1:0; coutresendl; return 0; POJ 3636 这个问题的顺序至关重要！为什么要对W和H的排序进行相反的操作！你可以想象一下在途中，你的遍历次序是从左下角走到右上角的，你选择反链数目的时候，必然是从斜对角线开始的！#include #include #include #include using namespace std;const int MAX_m = 10000;struct Doll int w, h; Doll(int _w, int _h) w = _w; h = _h; ;bool cmpWinc(const Doll& a, const Doll& b) return a.w b.h; ;int main() int C; scanf(%d, &C); for (int c = 0; c C; c+) int m; scanf(%d, &m); vector SW; for (int i = 0; i m; i+) int w, h; scanf(%d %d, &w, &h); SW.push_back(Doll(w, h); sort(SW.begin(), SW.end(), cmpWinc); multiset SH; vector N; int a = m; / Look at dolls from narrowest to widest for (int p = 0; p m; p+) / Find a tallest shorter doll from the narrower dolls if (SH.upper_bound(SWp) != SH.end() / Put it inside this doll SH.erase(SH.upper_bound(SWp); a; N.push_back(SWp); / If the next doll is wider, / enter all seen dolls into set of dolls to consider for insertion if (p+1 m & SWp.w SWp+1.w) SH.insert(N.begin(), N.end(); N.clear(); printf(%dn, a); POJ 1548#include #include #include using namespace std;struct Point int x; int y;int cmp(Point a,Point b) if(a.x=b.x) return a.y b.y; else return a.xb.x;int main() /freopen(robots.in,r,stdin); vector P; Point temp; while(cintemp.xtemp.y& temp.x!=-1 & temp.y!=-1) if(temp.x=0& temp.y=0) sort(P.begin(),P.end(),cmp); int dp10000; memset(dp,0,sizeof(dp); for(int i=0;iP.size();i+) if(dpi=0) dpi=1; Point cut=Pi; for(int j=i+1;jP.size();j+) if( dpj=0 & (cut.x=Pj.x & cut.y=Pj.y ) ) dpj=-1; cut=Pj; int res=0; for(int i=0;iP.size();i+) res+=dpi=1?1:0; coutresendl; P.clear(); else P.push_back(temp); return 0; 总结：把数据的关系组织成偏序集本身就是一个比较好的思想，然后根据数据的特征使用Dilworth 定理来做！ 这里需要注意的是，当数据集的偏序关系中存在相等的时候，它的排序是二维上升的！ 当偏序关系是严格不等的时候，这时候要注意了，从下图中，很显然看出，我们的偏序关系选取需要时一维上升，一维下降的！标签： POJ这篇文章发布于 2011年05月26日，星期四，20: