# Introduction

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

# 证明

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，有限偏序集的链的最大长度等于能划分集合的反链的最小数量。

# 代码

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include using namespace std; const int maxn = static_cast(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

### 代码

 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 using namespace std; typedef long long ll; const int maxn = static_cast(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

### 代码

 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 #include #include using namespace std; const int inf = 0x3f3f3f3f; const int maxn = static_cast(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; } }