【贪心】【DP】【Dilworth's theorem】 POJ 1065 Wooden Sticks

zorksylar — Sat, 17 Sep 2011 15:46:00 GMT

题目连接：

http://poj.org/problem?id=1065
题目大意：
有一堆树，每棵树有两个属性：(w,l)，求把这些树按照某种次序排列后的最小

setup time ，
定义当！（ wi < w i+1 && li < li+1)时，消耗一个setup time
(表达的不好，见谅)

分析：

Dilworth's theorem
参考

http://hi.baidu.com/lambda2fei/blog/item/6001f64476ae852acffca3be.html Orz

Dilworth定理说的是：对于一个偏序集，其最少链划分数等于其最长反链的长度。

Dilworth定理的对偶定理说的是：对于一个偏序集，其最少反链划分数等于其最长链的长度。

Dilworth定理先不证，有空再不上来，其对偶定理证明如下：

设一个偏序集S的最少反链划分数是p，最长链长度是r。

1.先证p≥r。这是显然的，因为最长链长度是r，r个元素中的任意两个都可以比较，因此它们必定两两属于不同的反链，因此反链个数≥r，即p≥r。

2.再证r≥p。设X1=S。找出X1的所有极小元组成集合Z1，将其从X1删之，得到X2，再找出X2的所有极小元组成集合Z2（特别注意Z2中的任何元素a2，在X1中必然存在一个元素a1使得a1≤a2，否则a2可以放到X1中，这与X1的选取矛盾），再将Z2从X2中删除，得到X3，……这样一直下去，总存在一个k使得XK不空但X(K+1)为空。这样便得到一条链a1，a2，a3，……，ak，其中ai属于Xi。由于r是最长链长度，因此r≥k。另一方面，我们也得到了一个反链划分，即X1，X2，X3，……，XK。由于p是最少反链划分，因此k≥p。因此有r≥p。证毕。

这个题目的解就是这个定理证明的过程，
本题直接找最长反链就行了

直接排序方法：

动态规划方法：

zorksylar 2011-09-17 23:46 发表评论

C++博客-不想当大牛的菜鸟，不是好菜鸟

【贪心】【DP】【Dilworth's theorem】 POJ 1065 Wooden Sticks