n374. 8. 百岳健行 - 高中生程式解題系統

內容

岱宗夫如何？齊魯青未了。
造化鍾神秀，陰陽割昏曉。
蕩胸生曾雲，決眥入歸鳥。
會當凌絕頂，一覽眾山小。
－杜甫

　　翻遍崇山峻嶺、賞盡萬千美景，生活在地貌壯麗的福爾摩沙，登山健行成了許多人休閒的項目之一。
　　莊中旅行社蒐集了臺灣百岳各處知名景點的旅遊資訊，共統整了 $N$ 個景點，其中包含了每個景點的海拔 $h_{1}, h_{2}, \dots, h_{N}$ ，以及它們之間是否有步道相連。旅行社希望設計一款應用程式，讓使用者輸入想去的 $D$ 個景點 $a_{1}, a_{2}, \dots, a_{D}$ 就能由此規劃出一條經過 $x$ 個景點的路線 $w_{1}, w_{2}, \dots, w_{x}$ ，其中這條路線要符合：
1. 沿途經過的景點海拔必須嚴格遞增 $h_{w_{i}} < h_{w_{j}}$ （ $1 \leq i < j \leq x$ ）。
2. 此路徑包含了最多使用者想去的景點，換句話說，無法再找到另一條合法的路徑，使該路徑包含更多的 $a_{i}$ 。
3. 在所有符合上述條件的路徑中，使此路徑經過的景點數最多( $x$ 最大)。

　　若景點與步道如上圖，且使用者想去三個景點 $2, 3, 4$ ，不過並沒有一條海拔嚴格遞增的路徑都經過這三個點，我們可以選擇路徑 ${5, 1, 2, 4, 8, 7}$ 或 ${5, 3, 4, 8, 7}$ ，它們各經過兩個使用者想去的點，又因為前者經過的總景點數較後者多，故應用程式會給使用者 ${5, 1, 2, 4, 8, 7}$ 這條路徑，請輸出該路徑總共包含多少個使用者想去的景點，以及該路徑一共經過多少景點，兩個整數以一個空白隔開。

輸入說明

　　輸入的第一行有兩個正整數 $N, M$ （ $1 \leq N \leq 1000, 0 \leq M \leq \frac{N \times (N - 1)}{2}$ ），代表一共有 $N$ 個景點與 $M$ 條步道。第二行有 $N$ 個整數 $h_{i}$ （ $1 \leq h_{i} \leq 10^{9}$ ）， $h_{i}$ 代表第 $i$ 個景點的海拔，保證所有景點的海拔高度皆不同。接下來 $M$ 行，每行有兩個相異的整數 $a b$ （ $1 \leq a, b \leq N$ ），代表景點 $a b$ 之間有一條步道連接。
　　接著有一個正整數 $Q$ （ $1 \leq Q \leq 500$ ），代表一共有 $Q$ 筆詢問，每筆詢問各有一行，該行的第一個整數 $D$ （ $1 \leq D \leq 500$ ）代表此筆詢問使用者想去的景點數，接下來的 $D$ 個整數 $a_{i}$ （ $1 \leq a_{i} \leq N$ ），為使用者想去的 $D$ 個景點，保證每筆詢問當中的 $D$ 個景點不重複。

輸出說明

　　對於每筆詢問，請輸出兩個整數 $t x$ 於一行， $t$ 代表應用程式計算出的路徑總共包含多少個使用者想去的景點， $x$ 為該路徑一共經過多少景點，兩個整數以一個空白隔開。

範例輸入 #1

8 10
5 8 9 11 3 16 20 15
1 2
2 4
3 4
3 5
3 6
5 1
5 6
6 7
7 8
8 4
1
3 2 3 4

範例輸出 #1

2 6

測資資訊：

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

提示：

本題共有 $4$ 個子題，每個子題有多筆測資。
第一子題：　 $D = Q = 1$ ，全部解出可得 $10$ 分。
第二子題：　 $D = 1$ ，全部解出可得 $10$ 分。
第三子題：　 $Q = 1$ ，全部解出可得 $10$ 分。
第四子題：　無其它限制，全部解出可得 $70$ 分。

標籤:

出處:

112學年度新北新莊高中校內資訊學科能力競賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

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