旅行推銷員問題是一個經典問題，給定 $N$ 座城市，我們從一座城市出發，經過所有其它城市恰好一次，最後再返回起點城市；在所有的路線中，我們想要找到行走總距離最短的路線。大明最近在研究如何求解旅行推銷員問題，有朋友跟他提出一個推測，一條候選路線和最佳路線的結構越相似，則該候選路線的總距離會越短。
大明對這個推測很感興趣，他想了一個分析的手法如下：
- 首先，他定義兩條路線的結構相似度為最長共同子序列的長度。令 $X_i$ 和 $X_j$ 代表兩條路線，$Xi=[𝑥_{𝑖,1},𝑥_{𝑖,2},\dots ,𝑥_{𝑖,𝑁}]$，$Xj=[𝑥_{j,1},𝑥_{j,2},\dots ,𝑥_{j,𝑁}]$。
若有一個 $X_i$ 和 $X_j$ 的共同子序列 $C$ 長度為 $K$，則 $C$ 可表示為 $C=[𝑥_{𝑖,𝑝_1},𝑥_{𝑖,𝑝_2},\dots ,𝑥_{𝑖,𝑝_𝐾}]=[𝑥_{j,𝑞_1},𝑥_{j,𝑞_2},\dots ,𝑥_{j,𝑞_𝐾}]$，其中 $1\le 𝑝_1<𝑝_2<\dots <𝑝_𝐾\le N$ 而且 $1\le 𝑞_1<𝑞_2<\dots <𝑞_𝐾\le 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\le s_i\le M$，$1\le i\le R$，滿足「相似度遞增、行走總距離遞減」的性質：
$l(X^*, 𝑋_{𝑠_𝑖})<l(X^*, 𝑋_{𝑠_{𝑖+1}})$ 而且 $d(𝑋_{𝑠_𝑖})>d(𝑋_{𝑠_{𝑖+1}})$，$1\le i\le 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)\rightarrow (7,120)\rightarrow (8,100)$，其集合大小為 $3$。{$X_6$, $X_3$, $X_4$, $X_1$} 也滿足性質：$(4,210)\rightarrow (6,150)\rightarrow (7,120)\rightarrow (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$ 的整數值。測資保證只會有一個路徑有最短行走總距離。
輸出所有滿足大明所要性質的解集合中的最大解集合的大小。
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
4
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
5
公開 測資點#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
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||