poj1065专题

贪心+偏序定理 poj1065+poj3636

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

poj1065 贪心

如题:http://poj.org/problem?id=1065 Wooden Sticks Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 19547 Accepted: 8246 Description There is a pile of n wooden sticks. The length an