题意：一堆doll，当一个doll的长和宽都比另一个doll小时，则小的可以放在大的里面。问最后剩下的doll的最小值。
解法：偏序集的两个定理：
定理1> 令(X,≤)是一个有限偏序集,并令r是其最大链的大小,则X可以被划分成r个但不能再少的反链.
其对偶定理称为Dilworth定理：
定理2> 令(X,≤)是一个有限偏序集，并令m是反链的最大的大小,则X可以被划分成m个但不能再少的链.
说白了就是链的最少划分数=反链的最长长度.
给定n个二元组(x, y),问存在最少多少个划分使得每个划分里面的二元组都满足x1<=x2并且y1<=y2。
如果定义x1<=x2&&y1<=y2为偏序关系的话,那么问题就转化成求这个集合的链的最少划分数.可以通过找最长反链长度来解决,这里的反链关系是x1>x2||y1>y2,
如果把n个二元组按照x递增排序,相同的x按照y递增排序,那么我们只需对y找到一个最长递减子序列就是所求的答案,复杂度O(nlogn)。对于相同的x之所以按照
y递增排序是因为这里偏序关系带等号,这样相同的x其实可以划分到一起,把y按照递增排序就可以使得相同的x最多只选择一个y。还有的题目要求满足x1<x2&&y1<y2,
这就需要把偏序关系相应修改。修改之后对于相同的x,每一个都会被划分到不同的集合(因为相等是不满足偏序关系的),所以这里的排序关系要改一下,x相同的y要按
照降序排列(如果y不是降序的话,假设y1<y2,我们很有可能先去放下y1,然后在把y2放在y1的后面,这样事实上是不合法的),这样求一个最长不递增子序列就是答案,
y递减保证可能会有多个x相同的二元组选入到结果中。
对于这题,先按照w升序排序,当w相等时再按照h降序排序,然后就是对序列h求解最长不递增子序列了。
关于二分法求最长不递增子序列，参考：http://www.cppblog.com/Davidlrzh/articles/137592.html
源代码
1
#include<iostream>
2#include<algorithm>
3
4using namespace std;
5
6const int MAXM = 20001;
7const int INF = 10005;
8
9struct Doll
10
{
11
int w;
12 int h;
13
};
14
15Doll dolls[MAXM];
16int b[MAXM]; //b[i]表示子序列长度为i时，最小的末元素，注意b[i]是不递增的，证明见博客。
17
18bool com(Doll d1, Doll d2) //比较函数
19{
20 if(d1.w == d2.w)
21
{
22 return d1.h > d2.h;
23
}
24 return d1.w < d2.w;
25}
26
27int LDS(int n) //二分法求解最长不递增子序列
28{
29 int left,right,mid;
30 int len = 1;
31 b[0] = INF;
32 b[1] = dolls[0].h;
33 for(int i=1; i<n; i++)
34 {
35 left = 0;
36 right = len;
37 while(left<=right) //二分法，在数组b中找出第一个比dolls[i].h小的数
38 {
39 mid=(left+right)>>1;
40 if(dolls[i].h <= b[mid])
41 {
42 left = mid + 1;
43 }
44 else
45 {
46 right = mid - 1;
47 }
48 }
49 b[left] = dolls[i].h;
50 if(left > len)
51 {
52 ++len;
53 }
54 }
55 return len;
56}
57
58int main()
59{
60 int t;
61 int m;
62
63 cin>>t;
64 while(t--)
65 {
66 cin>>m;
67 for(int i=0; i<m; i++)
68 {
69 cin>>dolls[i].w>>dolls[i].h;
70 }
71 sort(dolls,dolls+m,com);
72
73 cout<<LDS(m)<<endl;
74 }
75 return 0;
76}