题意:一堆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
4
using namespace std;
5
6
const int MAXM = 20001;
7
const int INF = 10005;
8
9
struct Doll
10

{
11
int w;
12
int h;
13
};
14
15
Doll dolls[MAXM];
16
int b[MAXM]; //b[i]表示子序列长度为i时,最小的末元素,注意b[i]是不递增的,证明见博客。
17
18
bool 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
27
int 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
58
int 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
}