题意：每个物品有两个属性：长和宽（长宽不可互换）。如果一个物品的长和宽均大于另一个物品，则这个物品可以罩住另一个物品，用这种罩住物品的方法将物品分组，一组之内的物品可以一个罩住一个的全部罩起来。问最少分成几组？
分析：通常这种问题是问物品最多的一组有多少个，这个问题则稍有不同。有人说要用到Dilworth定理，个人认为没什么关系。我们的做法是将物品先按照长从小到大排序。还有一个数组，用来存储当前每个分组的罩在最外层的长和宽，开始该数组为空。然后从小到大每次取出所有长度相等的物品，扣在当前的分组数组中的物品上，更新数组中存储的长宽值。这样长度相等的一起扣，在判断能不能扣的上的时候就不需要考虑长度了，之前扣好的都是长度小于当前物品的。在扣的过程中要注意发挥每个物品的最大能力，即让每个物品扣住刚好比它小一点点的物品。因为假设如果物品X不去扣比它小一点的那个物品A，而去扣比它小很多的那个物品B。而另一个物品Y，本来只能扣B不能扣A，又因为B已经被X扣了，Y只能单成一组，造成组数增加。在实际操作中是先拿当前长度的那个宽度最大的，发挥其最大作用，然后宽度次大的……为了程序实现起来简便，我们可以直接将所有物品按长度升序，宽度降序来排序，这样每次取出一个物品加入到分组中，就相当与我们刚才的操作了。
#include <cstdio>
#include <algorithm>
using namespace std; #define MAX_DOLL_NUM 20004 struct Doll
{
int width, height;
}doll[MAX_DOLL_NUM], chain[MAX_DOLL_NUM]; int doll_num;
int chain_cnt; bool operator < (const Doll &a, const Doll &b)
{
if (a.width == b.width)
return a.height > b.height;
return a.width < b.width;
} void input()
{
scanf("%d", &doll_num);
for (int i = ; i < doll_num; i++)
scanf("%d%d", &doll[i].width, &doll[i].height);
} bool fit(Doll a, Doll b)
{
return a.width > b.width && a.height > b.height;
} void work()
{
chain_cnt = ;
for (int i = ; i < doll_num; i++)
{
bool fitted = false;
for (int j = ; j < chain_cnt; j++)
if (fit(doll[i], chain[j]))
{
fitted = true;
chain[j] = doll[i];
//printf("%d %d\n", i, j);
//printf("%d %d %d %d\n", doll[i].width, doll[i].height, chain[i].width, chain[i].height);
break;
}
if (!fitted)
{
//printf("%d %d\n", doll[i].width, doll[i].height);
chain[chain_cnt++] = doll[i];
}
}
} int main()
{
int t;
scanf("%d", &t);
while (t--)
{
input();
sort(doll, doll + doll_num);
work();
printf("%d\n", chain_cnt);
}
return ;
}