[OI笔记] 最长上升子序列与网络流建模

与最长上升子序列相关的网络流问题:

给定一个序列 A[1..n] ,求出 A 的最长上升子序列长度。并且回答下列询问:

(1) 如果每个点只能用一次,能从 A 中取出几个最长上升子序列?

(2) 如果第 1 个点和第 n 个点可以用任意次,能从 A 中取出几个最长上升子序列?

(3) 如果每个点有一个删除代价 Bi ,最小需要花费多少代价,才能使 A 的最长上升子序列至少减少 1 ?

首先,最长上升子序列问题使用 DP 来求解,从后向前枚举 i ,求出 f[i] 表示以 i 为开头的最长上升子序列长度。最大的 f[i] 就是整个序列的最长上升子序列长度。

对于后续的 3 个问题,我们使用网络流求解:

对于序列中的每个点,我们将其拆成两个点 i 与 i' 。

对于每个 i ,如果 f[i] == Len(整个序列的最长上升子序列长度),我们就连边 S 到 i,如果 f[i] == 1,我们就连边 i' 到 T。

对于每个 i ,对于每个 (j > i) && (A[j] > A[i]) && (f[j] == f[i] - 1) ,我们从 i' 向 j 连边。

然后,我们对每个 i 到 i' 连边,并限制它的容量。如果所有的容量都限制为 1 ,就相当于每个点只能用一次。

这样,求出的最大流,就是能够取出的最长上升子序列个数。问题(1)

如果去掉 1->1' 和 n -> n' 的容量限制,就可以任意次使用这两个点。问题(2)

如果对于每个 i -> i' ,设置的容量限制为删除 i 点的代价,其余所有边都是正无穷的容量,那么就相当于,割掉一些 i 到 i' 的边。使得没有从 S 到 T 的路径且花费最少。

这样就是一个最小割模型了,还是求最大流。问题(3)

上一篇:Python的面向对象1


下一篇:在Docker中安装和部署MongoDB集群