解決建築橋樑的最長的次序子序列

我有些事情讓我困擾。我試圖解決建築橋樑問題，它有這些信息作爲指導。解決建築橋樑的最長的次序子序列

建橋
考慮具有穿過其中心的水平河流2-d地圖。南岸有n個城市，x座標爲a（1）... a（n），北岸有n個城市，x座標爲b（1）... b（n）。
您希望儘可能多的連接南北方向的城市與橋樑，使得沒有兩座橋樑交叉。當連接城市，你只能在北岸連接城市i到城市我在南岸「

我做了對堆棧溢出的研究，發現了一些話題，真正幫助了我很多，如：
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，或者在這方面有什麼異常，這對建橋問題不起作用？

來源

2013-10-19 user2898386

您可能已將x座標與訂單索引混淆了。用x座標10,20，... 70嘗試一個例子，它可能更明顯。 –

謝謝jwpat7。我真的很困惑。：D – user2898386

我的理解是，您使用的最長遞增子正確解決了問題：

enter image description here

你可以建立所有5個黑橋（而不是2級紅色的）。

爲什麼你認爲你只能做3座橋？

來源

2013-10-19 19:13:19

該指示說你只能將北岸的城市i連接到我在南岸的城市i「所以我認爲我們必須在兩邊連接相同的數字我誤解了指令的原因if當我重新檢查原始序列時 Northern Bank >> 7 4 3 6 2 1 5 Southern Bank >> 5 3 2 4 6 1 7 我只能連接3,2,1或3,6， 1或4,6,1只有 – user2898386

原來的序列是說，x 7.0的北部城市1只能連接到南部城市1在x 5.0，北部城市2在4.0只能連接到南部城市2在x 3.0等換句話說，原始序列指定了7個可能的橋的位置 - 我的圖中所示的那些橋的位置，注意我圖中的數字是x位置，城市指數沒有顯示出來 –

謝謝彼得·裏瓦茲。我現在明白了。你的回答確實對我很有幫助。 – user2898386

解決建築橋樑的最長的次序子序列

回答

相關問題