algorithm - 最长递增子序列解决建筑桥梁问题

Question

有件事让我很烦恼。我正在尝试解决将此信息作为说明的建筑桥梁问题。

Building Bridges
Consider a 2-D map with a horizontal river passing through its center. There are n cities on the southern bank with x-coordinates a(1) ... a(n) and n cities on the northern bank with x-coordinates b(1) ... b(n).
You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city i on the northern bank to city i on the southern bank."

我研究了 Stack Overflow，发现了一些对我有很大帮助的主题，例如:
Building bridges problem - how to apply longest increasing subsequence?和
How to determine the longest increasing subsequence using dynamic programming?

但是当我想出 LIS 并尝试手动解决一个样本列表时。假设我有

Northern Bank >> 7 4 3 6 2 1 5
Southern Bank >> 5 3 2 4 6 1 7

排序后的南岸

Northern Bank >> 1 3 4 6 7 2 5 
Southern Bank >> 1 2 3 4 5 6 7

假设 LIS 长度为“5”但实际上在第一个列表中，只有 3 个桥可以创建 (3,2,1)。那么我是否误解了 LIS 或是否有任何异常(exception)情况不适用于构建桥梁问题？

Answer 1

我的理解是你已经使用最长递增子序列正确地解决了这个问题:

您可以 build 所有 5 座黑色桥梁(但不能 build 2 座红色桥梁)。

为什么你认为你只能造 3 座桥？