poj3636专题

贪心+偏序定理 poj1065+poj3636

所谓的偏序定理 说的就是 Dilworth定理       给定n个二元组(x, y),问存在最少多少个划分使得每个划分里面的二元组都满足x1 <= x2并且y1 <= y2。   如果定义x1 <= x2 && y1 <= y2为偏序关系的话,那么问题就转化成求这个集合的链的最少划分数。可以通过找最长反链长度来解决,这里的反链关系是x1 > x2 || y1 > y2。如果把n个二元组按照x