首页
Python
Java
前端
数据库
Linux
Chatgpt专题
开发者工具箱
poj3636专题
贪心+偏序定理 poj1065+poj3636
所谓的偏序定理 说的就是 Dilworth定理 给定n个二元组(x, y),问存在最少多少个划分使得每个划分里面的二元组都满足x1 <= x2并且y1 <= y2。 如果定义x1 <= x2 && y1 <= y2为偏序关系的话,那么问题就转化成求这个集合的链的最少划分数。可以通过找最长反链长度来解决,这里的反链关系是x1 > x2 || y1 > y2。如果把n个二元组按照x
阅读更多...