我有事困扰我。我正在尝试解决以这些信息为指导的建筑桥梁问题。
建造桥梁
考虑一张 2-D 地图，其中有一条水平河流穿过其中心。南岸有 n 个城市，x 坐标为 a(1) ... a(n)，北岸有 n 个城市，x 坐标为 b(1) ... b(n)。
您希望通过桥梁连接尽可能多的南北城市对，以使没有两座桥梁交叉。连接城市时，只能连接北岸i市和南岸i市。”
我对 Stack Overflow 进行了研究，发现了一些对我有很大帮助的主题，例如：
搭建桥梁问题 - 如何应用最长递增子序列？
以及
如何使用动态规划确定最长的递增子序列？
但是当我想出 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，或者有任何例外不适用于构建桥梁问题？
