拟阵和贪心

发表于 更新于 分类于 阅读次数：

理论基础

一个拟阵是一个二元组 \(M = (U, I)\) ，其中 \(U\) 是一个有限集合，一般是待研究元素的全集，\(I\) 是 \(U\) 的一些子集的集合，一般是满足给定限制的子集的集合。

另外，拟阵要满足两个性质：

  • 遗传性： \(\forall S \in I, T \subseteq S\) 满足 \(T \in I\) 。
  • 交换性： \(\forall A \in I, B \in I, |A| < |B|\) 满足 \(\exists x \in B, x \notin A\) 使得 \(A \cup \{x\} \in I\) 。

有一部分贪心可以为这样的形式：给定一个映射 \(f: U \rightarrow R\) ，要在 \(I\) 中找到一个 \(S\) 使得 \(\sum_{x \in S} f(x)\) 最大。

这类贪心都可以用如下流程解决：

  1. 设 \(U_0 := U\) 表示可选集合，\(S := \varnothing\) 表示要求的集合。
  2. 在集合 \(U_0\) 中找出 \(f(x)\) 最大的元素 \(x\) 。
  3. 如果 \(S \cup \{x\} \in I\) ，令 \(S := S \cup \{x\}\) 。
  4. 令 \(U_0 := U_0 \setminus \{x\}\) ，若 \(U_0\) 非空，返回第 2 步。

证明

咕咕咕。

例子 1

Kruskal 求最小生成树。

咕咕咕。

例子 2

CQOI2013 新 Nim 游戏。

咕咕咕。