Introduction

cf 502场 C的一道构造题背后的离散数学原理:Dilworth定理

题意

构造一个排列,使得$LIS+LDS$最小, 例如: n=22 vaild permutation: 19 20 21 22 15 16 17 18 11 12 13 14 7 8 9 10 3 4 5 6 1 2 LIS=4 LDS=6

思路

构造方法:$[LIS]<[LIS]<[LIS]<\cdot \cdot \cdot <[LIS]$, 显然 如何证明取$LIS=\sqrt{n}, LDS=\left \lceil \frac{n}{LIS} \right \rceil$时构造出的$LIS+LDS$最小。

证明

  1. Partially order set
  2. 在偏序集(X,<)中,如果两个元素a, b,有关系a<b或b<a,则称a,b是可比的,否则称为a, b是不可比的
  3. An antichain in a partially ordered set is a set of elements no two of which are comparable to each other;
  4. A chain is a set of elements every two of which are comparable;
  5. Dilworth’s theorem: In any finite partially ordered set, the maximum number of elements in any antichain equals the minimum number of chains in any partition of the set into chains. 在任何有限偏序集中,反链的最大长度等于把集合划分成链的最小数量。
  6. Dual of Dilworth’s theorem (Mirsky’s theorem):the size of the largest chain in a partial order (if finite) equals the smallest number of antichains into which the order may be partitioned,有限偏序集的链的最大长度等于能划分集合的反链的最小数量。

本题中的偏序集({permutation N}, <), 每个[LIS]是反链,[LDS]是链,反链划分了这个集合,要求LIS+LDS

根据定理的对偶形式:LDS = numbers of [LIS], 最长链就是每块[LIS]贡献仅有一个元素,有LIS*LIS=n, LIS=sqrt(n),有LDS=ceil(n/sqrt(n))

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int maxn = static_cast<int >(2e5 + 7);
int a[maxn];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n; cin >> n;
    int L = sqrt(n + 0.5);
    int num = n / L;
    int cnt = 1;
    for (int i = 1; i <= num; i++)
        for (int j = 1; j <= L; j++, cnt++)
            a[cnt] = n - L * i + j;
    int re = n % num;
    if (n % num)
        for (int i = 1; i <= n % num; i++)
            a[cnt++] = i;
    for (int i = 1; i <= n; i++) printf("%d%c", a[i], "\n"[i == n]);
}

练习

HDU 3335 Divisibility

题意&思路

给出$n$个数(long long), 求出最大的集合的大小,在这个集合中元素之间不存在整除关系。 本题的偏序集{(n个数),整除} 要求反链的最大长度,应用定理需要找出最小数量的划分子集 例如: >1 2 3 => 1 2|3 ans=2 找出最小数量的集合划分,其中集合中的任意两个元素有整除关系 2 3 4 5 6 9 => 2 4|3 6|5|9 ans=4

此处暴力$n^2$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = static_cast<int>(1e3 + 7);
ll a[maxn];
int vis[maxn];

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    for (int kase = 1; kase <= t; kase++) {
        int n; cin >> n;
        for (int i = 0; i < n; i++)cin >> a[i], vis[i] = 0;
        sort(a, a + n);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue;
            ll tmp = a[i];
            ans++, vis[i] = 1;
            for (int j = i + 1; j < n; j++)
                if (a[j] % tmp == 0)
                    tmp = a[j], vis[j] = 1;
        }
        cout << ans << endl;
    }
}

POJ 1065

题意&思路

给出n个木棍,我们定义加工这些木棍所需要的时间为:加工第一根木棍需要时间1, 随后的木棍如果长度和重量都大于等于上一根,则不需要额外时间,否则需要额外时间1来调整机器,问一个最小的操作时间。例如: >5 4 9 5 2 2 1 3 5 1 4 3 2 2 1 1 2 2 3 1 3 2 2 3 1

本题的偏序集 (X,Y,<) 求的是链的个数 应用定理:在任何有限偏序集中,反链的最大长度等于把集合划分成链的最小数量 所以本题我们可以求按第一关键字排序后,第二关键字严格递减的最长长度。这里我们求解采用dp+二分,复杂度$nlogn$

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = static_cast<int >(5e3 + 7);

struct node {
    int w, l;
} a[maxn];

bool cmp(node cx, node cy) { return cx.l == cy.l ? cx.w < cy.w : cx.l < cy.l;}
int dp[maxn], pp[maxn];

unsigned long LIS(int *v, int n, int isStrict) {
    memset(dp, inf, sizeof(dp));
    for (int i = 0; i < n; i++)
        if (isStrict) *lower_bound(dp, dp + n, v[i]) = v[i];
        else *upper_bound(dp, dp + n, v[i]) = v[i];
    return lower_bound(dp, dp + n, inf) - dp;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int t; cin >> t;
    for (int kase = 1; kase <= t; kase++) {
        int n; cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i].l >> a[i].w;
        sort(a, a + n, cmp);
        for (int i = n - 1, j = 0; ~i; i--, j++) pp[j] = a[i].w;
        cout << LIS(pp, n, 1) << endl;
    }
}

参考

  1. https://www.wikiwand.com/en/Dilworth’s_theorem