[关闭]
@LinKArftc 2015-05-05T13:43:12.000000Z 字数 6528 阅读 3151

链-反链-Dilworth定理

数论 算法

一些概念：

偏序

设A是一个非空集，P是A上的一个关系，若关系P是自反的、反对称的、和传递的，则称P是集合A上的偏序关系。
即P适合下列条件：

  • 对任意的a∈A,(a,a)∈P;
  • 若（a,b)∈P且（b,a)∈P,则a=b;
  • 若（a,b)∈P,(b,c)∈P,则（a,c)∈P

则称P是A上的一个偏序关系。

偏序集

We define a Partially Ordered Set, or a Poset, as a set P with a partial ordering  defined on it’s elements. I.e, for any two elements x and y of P, either x ≤ y, y ≤ x (x and y are comparable), or x || y (x and y are incomparable).
简单说就是带偏序关系的集合A称为偏序集或半序集。

链（chain）

一个偏序集S的全序子集（所谓全序是指任意两个元素可比较）

反链（antichain）

一个偏序集S的子集，其中任意两个元素不可比较

极大（maximal）链

对一个链C，如果找不到另一个链C'，使得C是C'的真子集，那么称链C是极大的

极大（maximal）反链

对一个反链A，如果找不到另一个反链A'，使得A是A'的真子集，那么称反链A是极大的

最大链（maximum/longest）

链C包含元素个数不少于任意其他链C'，则C是最大链

最大反链（maximum/largest）

类似最大链定义

  • （易见，最大链必然是极大链，最大反链必然是极大反链，可以用反证法）

偏序集S的最大链的大小称为偏序集S的高度（height）

偏序集S的最大反链的大小称为偏序集S的宽度（width）

例：(A,≤)是偏序集，其中A={1,2,3,4,5}，其中≤是整除关系，那么对任意的x∈p都有1≤x,所以1和1,2,3,4,5都是可比的，但是2不能整除3，且3不能整除2，所以2和3是不可比的。
在X中，对于元素a，如果任意元素b，由b≤a得出b=a，则称a为极小元。
一个反链A是X的一个子集，它的任意两个元素都不能进行比较。
一个链C是X的一个子集，它的任意两个元素都可比。

两个重要定理

  • 定理1
    令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
    其对偶定理称为Dilworth定理：
  • 定理2
    令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

说白了就是 链的最少划分数 = 反链的最长长度

相关题目练习

poj 1065 Wooden Sticks

  • 题意：有n条木棒，给出它们每条的l和w，用一台机器对它们进行加工，如果机器正加工的木条，与在它之前加工的木块有关系：l <= l'和w <= w'，则机器不用准备时间，否则需准备1分钟。问加工完全部木棒，机器最少需要准备多久。
  • 要求的就是集合的chain的划分最小数目.
    对于题目中给出的关系P={l <= l’ and w <= w’}, 我们定义关系P’={l < l’ and w > w’} (并不是l<=l’), 那么对于原来关于 P 可比较的两个元素, 关于 P’ 则不能比较, 原来不能比较关于 P’ 就可比较. 相应的 P 的 chain/antichain 就成为 P’ 的 antichain/chain .
    这样定义后, 就可以放下原题, 题目变成找一堆元素中的最少antichain数目, 根据Dilworth定理对偶定理的证明过程(如上), 每次剥离出 Xi 中的所有极小元, 直到 Xi 为空, 剥离的次数就是答案 .
    剥离的次数 == k== 关于 P’ 的最长chain的长度(对偶定理) == 关于P的最长antichain的长度(chain转换) == 关于P的chain的最少划分数(Dilworth)
    有点绕.. 但比看上去简单
    因为P’是严格的偏序关系, 每次取出的最小元 x 就要满足找不到 y 使 y P’ x (如果是不严格的偏序就要考虑自反的情况)
    怎样取极小元呢, P’ 的极小元是 “在 l 比它小的元素中, 找不到 w 比它大的元素”, 按照代码中的 comp() 排序以后(先l后w), 以这个条件找极小元的集合, 等价于从第一个元素开始找, 后一个元素的w’>=前一个元素的w, 的元素集合. 比如(1,2) (2,3) (2,4) (3,5) (6,7), 满足2<=3<=4<=5<=7, 这样贪心就很简单了
  1. /*************************************************************************
  2.   > File Name: 1065.cpp
  3.   > Author: LinKArftc
  4.   > Created Time: 2015/5/4 LinK 05:12:26
  5. *************************************************************************/
  6. //思路：贪心。对length进行上升序列的排序，特别应注意两length相等时，应按weight的上升序列的排序。排序号之后，就是找出weight的最小上升序列数了。
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. struct Node {
  14.     int l, w, vis;
  15. } stick[5010];
  17. bool cmp(Node a, Node b) {
  18.     if (a.l < b.l) return true;
  19.     if (a.l > b.l) return false;
  20.     return a.w < b.w;
  21. }
  24. int main() {
  25. //    freopen("input.txt", "r", stdin);
  26.     int T, n;
  27.     int ans, cur;
  28.     scanf("%d", &T);
  29.     while (T --) {
  30.         scanf("%d", &n);
  31.         for (int i = 0; i < n; i ++) {
  32.             scanf("%d %d", &stick[i].l, &stick[i].w);
  33.             stick[i].vis = 0;
  34.         }
  35.         sort(stick, stick+n, cmp);
  36.         ans = 0;
  37.         for (int i = 0; i < n; i ++) {
  38.             if (!stick[i].vis) {
  39.                 ans ++;
  40.                 cur = stick[i].w;
  41.                 for (int j = i+1; j < n; j ++) {
  42.                     if (!stick[j].vis && stick[j].w >= cur) {
  43.                         cur = stick[j].w;
  44.                         stick[j].vis = 1;
  45.                     }
  46.                 }
  47.             }
  48.         }
  49.         printf("%d\n", ans);
  50.     }
  51.     return 0;
  52. }

poj 3636 Nested Dolls

  • 和1065基本一样, 有了上面的理论就很好做了. 关键在于 P => P’ 的转换
    P={w1 所以 P的”可比较”关系 Pc = {ww2 && h1>h2}
    所以 P’c= {w1=h2 || w1>w2 && h1<=h2 || w1==w2}
    所以 P’= {w1<=w2 && h1>=h2}
    这里 P’ 是具有自反性和反对称性的非严格偏序关系.
    这里就有一个问题: 集合内元素具有互异性, 但是题目中的元素有可能存在两两相同的, 怎么办?
    我们可以想像我们上面讨论的集合是题目中的元素”只保留相同元素中的一个”后的集合, 这个集合中的元素a包含了n个题目中的相同元素, 就有两种处理的方法:
    方法一: 把这n个元素看作一个a来”剥离”(取最小元), 1065就是这样, (1,2)(1,2)(1,2)在一起剥离是可以的, 因为1<=1,2<=2, 符合P的比较条件
    方法二: 剥离a后a还存在于后来的Xi中, 并且n-=1, 直到n==0 a消失, 3636就要这么干, (1,2)(1,2)是不能放在一起的, 不符题意(P), 可以证明这样干是最优的(如果不取这个最小元, 这次执行后得到的Xi要比取的元素多一个, 不取白不取)
    经过思考, 这道题最终要做的贪心是: 先按照w排序, w的互异值从小到大为w1,w2..wk, 然后在w==w1的元素里找到h最大的元素取出, 再在w2中找h最大的元素取出, 并且这些h需要满足条件:比前一个取出的元素的h大, 取完一次result++, 直到取空
  1. /*************************************************************************
  2.   > File Name: 3636.cpp
  3.   > Author: LinKArftc
  4.   > Created Time: 2015/5/4 LinK 06:47:50
  5.  *************************************************************************/
  7. #include <cstdio>
  8. #include <iostream>
  9. #include <cstring>
  10. #include <algorithm>
  11. using namespace std;
  13. struct Node {
  14.     int w, h, vis;
  15. } doll[20010];
  17. bool cmp(Node a, Node b) {
  18.     if (a.w < b.w) return true;
  19.     if (a.w > b.w) return false;
  20.     return a.h > b.h; //注意是降序。。。
  21. }
  23. int main() {
  24. //    freopen("input.txt", "r", stdin);
  25.     int T;
  26.     int n;
  27.     scanf("%d", &T);
  28.     while (T --) {
  29.         scanf("%d", &n);
  30.         for (int i = 0; i < n; i ++) {
  31.             scanf("%d %d", &doll[i].w, &doll[i].h);
  32.             doll[i].vis = 0;
  33.         }
  34.         sort(doll, doll + n, cmp);
  35.         int ans = 0;
  36.         for (int i = 0; i < n; i ++) {
  37.             if (!doll[i].vis) {     
  38.                 ans ++;
  39.                 int curW = doll[i].w;
  40.                 int curH = doll[i].h;
  41.                 for (int j = i+1; j < n; j ++) {
  42.                     if (!doll[j].vis && doll[j].h > curH && doll[j].w > curW) {
  43.                         curH = doll[j].h;
  44.                         curW = doll[j].w;
  45.                         doll[j].vis = 1;
  46.                     }
  47.                 }
  48.             }
  49.         }
  50.         printf("%d\n", ans);
  51.     }
  53.     return 0;
  54. }

poj 1548 Robots

  • 题意
    给定一个网格图，每次从左上角出发，只能往右或往下走，最后到达右下角，每个格子有最低经过次数，问最少走几次
  • 思路
    Dilworth定理：DAG（有向无环图）的最小链覆盖=最大点独立集
    最小链覆盖指选出最少的链(可以重复)使得每个点都在至少一条链中
    最大点独立集指最大的集合使集合中任意两点不可达
    此题中最大点独立集显然是一个集合满足集合中任意两点都是左下-右上的关系
    DP一遍就能出解 复杂度O(Tmn)
  2. /*************************************************************************
  3.   > File Name: 1548.cpp
  4.   > Author: LinKArftc
  5.   > Created Time: 2015/5/4 LinK 07:42:24
  6.  *************************************************************************/
  8. #include <cstdio>
  9. #include <iostream>
  10. #include <cstring>
  11. #include <algorithm>
  12. using namespace std;
  14. int map[30][30];
  16. int main() {
  17. //    freopen("input.txt", "r", stdin);
  18.     int a, b;
  19.     int row, col;
  20.     int flag = 0;
  21.     while (1) {
  22.         memset(map, 0, sizeof(map));
  23.         row = -1;
  24.         col = -1;
  25.         while (~scanf("%d %d", &a, &b)) {
  26.             if (a == -1 && b == -1) {
  27.                 flag = 1;
  28.                 break;
  29.             }
  30.             if (a == 0 && b == 0) break;
  31.             map[a][b] = 1;
  32.             row = max(row, a);
  33.             col = max(col, b);
  34.         }
  35.         if (flag) break;
  36.         int ans = -1;
  37.         for (int i = row; i >=1; i --) {
  38.             for (int j = 1; j <= col; j ++) {
  39.                 map[i][j] = max(map[i][j]+map[i+1][j-1], map[i][j-1]);
  40.             }
  41.             for (int j = 1; j <= col; j ++) {
  42.                 map[i][j] = max(map[i][j], map[i+1][j]);
  43.                 ans = max(ans, map[i][j]);
  44.             }
  45.         }
  46.         printf("%d\n", ans);
  47.     }
  48.     return 0;
  49. }

njoj 2015集训队春季邀请赛选拔赛 B题 A simple problem

  • 上面一道题的类似，稍微有点变化
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  7. int n, m;
  8. int map[1010][1010];
  10. int main() {
  11. //    freopen("input.txt", "r", stdin);
  13.     int T;
  14.     scanf("%d", &T);
  15.     while (T --) {
  16.         memset(map, 0, sizeof(map));
  17.         scanf("%d %d", &n, &m);
  18.         for (int i = 1; i <= n; i ++) {
  19.             for (int j = 1; j <= m; j ++) {
  20.                 scanf("%d", &map[i][j]);
  21.             }
  22.         }
  23.         int ans = -1;
  24.         for(int j = 1; j <= m; j ++) {
  25.             for(int i = n; i > 0; i --)
  26.                 map[i][j] = max(map[i][j-1], map[i+1][j-1] + map[i][j]);
  27.             for(int i = n; i > 0; i --)
  28.                 map[i][j] = max(map[i][j], map[i+1][j]);
  29.             ans = max(ans, map[1][j]);
  30.         }
  31.         printf("%d\n", ans);
  32.     }
  34.     return 0;
  35. }

zoj 2283 Challenge of Wisdom

  • 题意和上面的类似，但数据要大很多，要用 vector 优化
  1. /*************************************************************************
  2.   > File Name: 2283.cpp
  3.   > Author: LinKArftc
  4.   > Created Time: 2015/5/5 LinK 05:53:54
  5. *************************************************************************/
  7. #include<cstdio>
  8. #include<iostream>
  9. #include<algorithm>
  10. #include<cstring>
  11. #include<vector>
  12. using namespace std;
  14. struct Node {
  15.     int x, y, vis;
  16. };
  18. int n, m, p;
  19. Node trea[100010];
  21. bool cmp(Node a, Node b) {
  22.     return (a.x != b.x) ? a.x < b.x : a.y < b.y;
  23. }
  25. int main() {
  26. //    freopen("input.txt", "r", stdin);
  27.     while (~scanf("%d %d %d", &n, &m, &p)) {
  28.         for (int i = 0; i < p; i ++) {
  29.             scanf("%d %d", &trea[i].x, &trea[i].y);
  30.             trea[i].vis = 0;
  31.         }
  32.         sort(trea, trea+p, cmp);
  33.         vector <int> v;
  34.         vector <int>::iterator it;
  35.         for (int i = 0; i < p; i ++) {
  36.             it = upper_bound(v.begin(), v.end(), trea[i].y);
  37.             if (it != v.begin()) {
  38.                 it --;
  39.                 *it = trea[i].y;
  40.             } else {
  41.                 v.insert(v.begin(), trea[i].y);
  42.             }
  43.         }
  44.         printf("%d\n", v.size());
  45.     }
  46.     return 0;
  47. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注