n135. p7. 旅行推銷員問題 - 高中生程式解題系統

內容

　　旅行推銷員問題是一個經典問題，給定 $N$ 座城市，我們從一座城市出發，經過所有其它城市恰好一次，最後再返回起點城市；在所有的路線中，我們想要找到行走總距離最短的路線。大明最近在研究如何求解旅行推銷員問題，有朋友跟他提出一個推測，一條候選路線和最佳路線的結構越相似，則該候選路線的總距離會越短。

　　大明對這個推測很感興趣，他想了一個分析的手法如下：

首先，他定義兩條路線的結構相似度為最長共同子序列的長度。令 $X_{i}$ 和 $X_{j}$ 代表兩條路線， $X i = [𝑥_{𝑖, 1}, 𝑥_{𝑖, 2}, \dots, 𝑥_{𝑖, 𝑁}]$ ， $X j = [𝑥_{j, 1}, 𝑥_{j, 2}, \dots, 𝑥_{j, 𝑁}]$ 。
若有一個 $X_{i}$ 和 $X_{j}$ 的共同子序列 $C$ 長度為 $K$ ，則 $C$ 可表示為 $C = [𝑥_{𝑖, 𝑝_{1}}, 𝑥_{𝑖, 𝑝_{2}}, \dots, 𝑥_{𝑖, 𝑝_{𝐾}}] = [𝑥_{j, 𝑞_{1}}, 𝑥_{j, 𝑞_{2}}, \dots, 𝑥_{j, 𝑞_{𝐾}}]$ ，其中 $1 \leq 𝑝_{1} < 𝑝_{2} < \dots < 𝑝_{𝐾} \leq N$ 而且 $1 \leq 𝑞_{1} < 𝑞_{2} < \dots < 𝑞_{𝐾} \leq N$ 。
下面的圖例分別代表兩種路線 $[1, 2, 3, 4, 5, 6, 7, 1]$ 和 $[1, 3, 4, 5, 2, 6, 7, 1]$ ，它們的最長共同子序列為 $[1, 3, 4, 5, 6, 7, 1]$ ，長度為 $7$ 。
接著，給定 $M$ 條路線 $X_{1}$ , $X_{2}$ , $\dots$ , $X_{M}$ ，令 $d (X_{i})$ 代表路線 $X_{i}$ 的行走總距離， $l (X^{*}, X_{i})$ 代表最短路線 $X^{*}$ 和路線 $X_{i}$ 的結構相似度，他想找到解集合 $S = {𝑋_{𝑠_{1}}, 𝑋_{𝑠_{2}}, \dots, 𝑋_{𝑠_{𝑅}}}$ ，其中 $1 \leq s_{i} \leq M$ ， $1 \leq i \leq R$ ，滿足「相似度遞增、行走總距離遞減」的性質：
$l (X^{*}, 𝑋_{𝑠_{𝑖}}) < l (X^{*}, 𝑋_{𝑠_{𝑖 + 1}})$ 而且 $d (𝑋_{𝑠_{𝑖}}) > d (𝑋_{𝑠_{𝑖 + 1}})$ ， $1 \leq i \leq R - 1$ 。

　　舉例來說，給定 $N = 7$ 座城市，城市 $1$ 為路線起點和終點。我們有六條路線，其中第一條路線為最短路線。

路線代號	路線內容	結構相似度 $l (X^{*}, X_{i})$	行走總距離 $d (X_{i})$
$X_{1} (X^{*})$	$1, 2, 3, 4, 5, 6, 7, 1$	$8$	$100$
$X_{2}$	$1, 7, 6, 5, 4, 3, 2, 1$	$3$	$200$
$X_{3}$	$1, 4, 3, 2, 5, 6, 7, 1$	$6$	$150$
$X_{4}$	$1, 3, 4, 5, 2, 6, 7, 1$	$7$	$120$
$X_{5}$	$1, 3, 2, 4, 7, 6, 5, 1$	$5$	$140$
$X_{6}$	$1, 6, 5, 4, 3, 2, 7, 1$	$4$	$210$

　　此例中，{ $X_{6}$ , $X_{4}$ , $X_{1}$ } 是一個滿足性質的集合： $(4, 210) \to (7, 120) \to (8, 100)$ ，其集合大小為 $3$ 。{ $X_{6}$ , $X_{3}$ , $X_{4}$ , $X_{1}$ } 也滿足性質： $(4, 210) \to (6, 150) \to (7, 120) \to (8, 100)$ ，其大小為 $4$ 。本例中能找到滿足性質的最大集合，其大小為 $4$ 。

　　大明認為這個 $S$ 內的解的個數越多，就越支持朋友的推測。請你撰寫一個程式，給定數個路線，計算從中能找到的最大 $S$ 的解個數。

輸入說明

　　第一列有兩個整數 $N$ ( $1 \leq N \leq 500$ ) 和 $M$ ( $1 \leq M \leq 500$ )，其中 $N$ 代表城市數目， $M$ 代表候選路線的數目。接下去有 $M$ 行，代表 $M$ 條路線的資訊：每行有 $N + 2$ 個以空白間隔的正整數值，第一個值為該路線的行走總距離，後續的 $N + 1$ 個值代表城市編號，第一個和最後一個數必為 $1$ ，其它數字為介於 $2$ 和 $N$ 的整數值。測資保證只會有一個路徑有最短行走總距離。

輸出說明

　　輸出所有滿足大明所要性質的解集合中的最大解集合的大小。

範例輸入 #1

7 6
100 1 2 3 4 5 6 7 1
200 1 7 6 5 4 3 2 1
150 1 4 3 2 5 6 7 1
120 1 3 4 5 2 6 7 1
140 1 3 2 4 7 6 5 1
210 1 6 5 4 3 2 7 1

範例輸出 #1

範例輸入 #2

7 6
200 1 7 6 5 4 3 2 1
130 1 4 3 2 5 6 7 1
120 1 3 4 5 2 6 7 1
140 1 3 2 4 7 6 5 1
210 1 6 5 4 3 2 7 1
100 1 2 3 4 5 6 7 1

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <1K
公開測資點#1 (5%): 2.0s , <1K
公開測資點#2 (5%): 2.0s , <1K
公開測資點#3 (5%): 2.0s , <1K
公開測資點#4 (5%): 2.0s , <1K
公開測資點#5 (5%): 2.0s , <1M
公開測資點#6 (5%): 2.0s , <1M
公開測資點#7 (5%): 2.0s , <1M
公開測資點#8 (5%): 2.0s , <1M
公開測資點#9 (5%): 2.0s , <1M
公開測資點#10 (5%): 2.0s , <1M
公開測資點#11 (5%): 2.0s , <1M
公開測資點#12 (5%): 2.0s , <1M
公開測資點#13 (5%): 2.0s , <1M
公開測資點#14 (5%): 2.0s , <1M
公開測資點#15 (5%): 2.0s , <1M
公開測資點#16 (5%): 2.0s , <1M
公開測資點#17 (5%): 2.0s , <1M
公開測資點#18 (5%): 2.0s , <1M
公開測資點#19 (5%): 2.0s , <1M

提示：

標籤:

LCS LIS

出處:

110 新北市資訊學科能力複賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」