题意：求二维偏序的最少链划分。
至于偏序集，链，反链等等概念可以参考这里:http://www.cnblogs.com/fstang/archive/2013/03/31/2991220.html
Dilworth定理的证明（英文的）：http://aleph.math.louisville.edu/teaching/2009FA-681/notes-091119.pdf
简要来说，设链的最小划分数为p，最长反链长度为l，证明分两步：
(1).p≥l。因为反链上任意两点都不可能在同一个链中，抽屉原理可知p≥l。
(2).p≤l。反复选择反链的极小元点集Xi从全集S中删除直到S为空，
每次阶段的选择的Xi则构成一个链划分，且最后一次删除的将会对应最长的反链。
这个链划分的大小为l，而p是最小链划分，所以有l≥p。
至于实现上，我采用的是O(nlogn)的逆向求LIS的方法。
（似乎根据证明第二步可以得出贪心做法，不过因为要排序时间复杂度还是O(nlogn)。
#include<cstdio> #include<iostream> #include<string> #include<cstring> #include<queue> #include<vector> #include<stack> #include<vector> #include<map> #include<set> #include<algorithm> //#include<bits/stdc++.h> using namespace std; const int N = 5e3+5; struct Stick { int l, w; bool operator <(const Stick &th) const{ return l < th.l || (l == th.l && w < th.w); } void IN(){ scanf("%d%d",&l,&w); } }stick[N]; int g[N]; //#define LOCAL int main() { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int T; cin>>T; while(T--){ int n; scanf("%d",&n); for(int i = 0; i < n; i++){ stick[i].IN(); } sort(stick,stick+n); memset(g,0x3f,sizeof(int)*n); int ans = 0; for(int i = n-1; i >= 0; i--){ int k = lower_bound(g+1,g+n-i,stick[i].w)-g; ans = max(ans,k); g[k] = stick[i].w; } printf("%d\n",ans); } return 0; }
原文：http://www.cnblogs.com/jerryRey/p/4885732.html