問題

在一塊電路板的上下兩端分別有n個接線柱。根據電路設計，要求用導線 （i，π（i）），將上端接線柱 i 與下端接線柱 π（i） 相連，

如圖，其中 π（i），1《=i《=n，是（1，2……，n）的一個排列。導線（i，π（i））稱為該電路板上的第i條連線。對于任何 1《=i《s《=n，第i條連線和第s條連線相交的充分且必要條件是 π（i） 》 π（s）。

ps：注意 π（pi） 和 n，不是小寫的n，別看錯了

問：在制作電路板時，要求將這n條線分布到若干個絕緣層上，在同一層上的連線不能相交。電路布線問題要確定將哪些連線安排在第一層上，使得該層上有盡可能多的連線。

詳細說明

首先 上下各有 n 個接線柱，用 a［i］ 數組表示 與 上接線柱 相連線的 下接線柱，再用 set［i］［j］ 表示上接線柱 i 與下接線柱 j 相連線的 左邊（包括 i ，j 連線）的最大不相交連線的個數。

ps（這里的 j ，i 和上面問題中說的不是一個東西，這里的 i指的是上接線柱，j指的是下接線柱）

1、公式如下：

如果 j ！= a［i］ 則 max（ set［i-1］［j］，set［i］［j-1］ ）

set［i，j］ =

如果 j == a［i］ 則 set［i-1］［j-1］ + 1

循環遍歷 i 和 j ，具體使用 i X j 的嵌套循環，其實就是每一個上接線柱和每一個下接線柱做一次匹配，這樣就可以得出結果，set［n］［n］即我們想要的結果。最后通過回溯把結果輸出出來

==》 j == a［i］，表示當上圖中的某個上下接線柱相連時，這時這兩個點不會在和其他的接線柱相連，

這時在 （i ，j） 處的最大不相交連線的個數就應該是就是 第 i-1個上接線柱 和第 j-1個下接線柱時的 最大不相交連線的個數 + 1。這個+1很重要。

==》 j ！= a［i］，表示當上圖中的某個上下接線柱相連時，這時 i 點和 非 j 點相連， j 點和 非 i 點相連，

這時在（ i ，j） 處的最大不相交連線的個數就應該和 （ i - 1，j ） 處最大不相交連線的個數、 （ i，j - 1）處最大不相交連線的個數中較大的最大不相交連線的個數相同。

2、參考圖如下：

紅色標明的就是算法選擇的路徑（向上優先，也可以用向左優先，答案都是四個，但值會有一點不同）。在斜角值改變時可以取得所求的子集。即 9-》10，7-》9， 5-》5， 3-》4

代碼塊

#include 《stdio.h》

#include 《stdlib.h》

#define MAX（ a， b ） （ （a） 》 （b） ？ （a） ： （b） ）

void circut（ int a［］， int set［］［11］， int n ）;

void back_track（ int i， int j， int set［］［11］ ）;

int main（）

{

int a［］ = { 0， 8， 7， 4， 2， 5， 1， 9， 3， 10， 6 };

int set［11］［11］;

circut（ a， set， 10 ）;

printf（ “max set： %d \n”， set［10］［10］ ）;

back_track（ 10， 10， set ）;

printf（ “\n” ）;

system（ “pause” ）;

return（0）;

}

void circut（ int a［］， int set［］［11］， int n ）

{

int i， j;

for （ i = 0; i 《 n; i++ ）

{

set［i］［0］ = 0;

set［0］［i］ = 0;

}

for （ i = 1; i 《= n; i++ ）

{

for （ j = 1; j 《= n; j++ ）

{

if （ a［i］ ！= j ）

set［i］［j］ = MAX（ set［i - 1］［j］， set［i］［j - 1］ ）;

else

set［i］［j］ = set［i - 1］［j - 1］ + 1;

}

}

}

void back_track（ int i， int j， int set［］［11］ ）

{

if （ i == 0 ）

return;

if （ set［i］［j］ == set［i - 1］［j］ ）

back_track（ i - 1， j， set ）;

else if （ set［i］［j］ == set［i］［j - 1］ ）

back_track（ i， j - 1， set ）;

else{

back_track（ i - 1， j - 1， set ）;

printf（ “（%d，%d） ”， i， j ）;

}

}

時間復雜度

circut 的時間復雜度為O（n2）

back_track的時間復雜度為 O（n）

如有錯誤請指正。