当前位置：首页 > news >正文

贡献转 $01$

news 2026/4/28 22:07:48

问题形式

定义将序列 $a$ 变成序列 $b$ 的代价是 $\sum_{i=1}^{m} |a_i - b_i|$。求使得序列 $b$ 满足条件 $A$ 的 $a$ 变成 $b$ 的最小代价。

适用条件

偏序限制：条件 $A$ 是形如若干 $a_i \le a_j$。
可差分：将 $x$ 变成 $y$ 的代价是 $|x - y|$。

做法

记 $a^k$ 是将 $a$ 序列中 $\le k$ 的数赋值成 $0$，将大于 $k$ 的数赋值成 $1$ 得到的新序列。答案是使所有 $k \in \mathbb{Z}$，$a^k$ 满足条件 $A$ 的最小代价的和。

证明

这是答案下界：记 $f(S)$ 表示将 $S$ 变成满足条件 $A$ 的最小代价。由条件 $2$ 可得，$|x - y| = \sum_{k \in \mathbb{Z}} |[x > k] - [y > k]|$，所以
$\sum_{i=1}^{n} |a_i - b_i| = \sum_{i=1}^{n} \sum_{k \in \mathbb{Z}} |[a_i > k] - [b_i > k]| = \sum_{k \in \mathbb{Z}} \sum_{i=1}^{n} |[a_i > k] - [b_i > k]|$，即由 $a$ 变 $b$ 的代价等价于对所有 $k \in \mathbb{Z}$，$a^k$ 变成 $b^k$ 的代价和。又由条件 1 可得，$b$ 合法的必要条件是对所有 $k \in \mathbb{Z}$, $b^k$ 合法。所以 $\sum_{k \in \mathbb{Z}} \sum_{i=1}^{n} |[a_i > k] - [b_i > k]| \ge \sum_{k \in \mathbb{Z}} f(a^k)$，即这是答案的一个下界。
能取到下界：记 $g^k$ 表示 $a^k$ 变成满足条件 $A$ 代价最小的一个 01 串。下界能取到等价于存在一个 $b$ 序列, 使得 $\forall k \in \mathbb{Z}, b^k = g^k$，而这等价于随着 $k$ 的减少，$\forall i \in [1,n]$，$g^k_i$ 不升，即每个位置恰好一次从 $0$ 变成 $1$。下面是构造性证明。将问题建模成最小割问题。将 $g^k_i$ 抽象成点 $i$，用源点和汇点分别表示选 $1$ 和选 $0$。如果 $a^k_i = 1$，将源点 $s$ 向点 $i$ 连容量为 $1$ 的单向边；如果 $a^k_i = 0$，将点 $i$ 向汇点 $t$ 连容量为 $1$ 的单向边。对于条件 $A$ 中所有偏序关系 $a_i \le a_j$，将点 $i$ 向点 $j$ 连容量为正无穷的边。那么 $f(a^k)$ 就等于该网络的最小割，并且对于最小割 $(S,T)$，如果点 $i \in S$，那么 $g^k_i = 1$，否则 $g^k_i = 0$。随着 $k$ 的减小，输入 $a^k$ 满足 $\forall i \in [1,n]$，$a^k_i$ 从 $1$ 变成 $0$ 恰好一次。所以每次 $k$ 减小 $1$，相当于将一些边 $(v,t,1)$，修改成 $(s,v,1)$，感性理解这只会使得 $S$ 不断扩大，所以随着 $k$ 的减小，每个点 $i$ 恰好从 $T$ 中归为 $S$ 一次，每个 $a^k_i$ 恰好从 $0$ 变成 $1$ 一次，对于下界的所有 $g^k$，必然能找到一个对应的 $b$，证毕。其中关于随着 $k$ 的减小，$S$ 只可能扩大的证明将在文末给出。