岱宗夫如何？齊魯青未了。
造化鍾神秀，陰陽割昏曉。
蕩胸生曾雲，決眥入歸鳥。
會當凌絕頂，一覽眾山小。
－杜甫
翻遍崇山峻嶺、賞盡萬千美景，生活在地貌壯麗的福爾摩沙，登山健行成了許多人休閒的項目之一。
莊中旅行社蒐集了臺灣百岳各處知名景點的旅遊資訊，共統整了 $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\le i<j\le 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\le N\le 1000, 0\le M\le \frac{N\times (N-1)}{2}$），代表一共有 $N$ 個景點與 $M$ 條步道。第二行有 $N$ 個整數 $h_i$（$1\le h_i\le 10^9$），$h_i$ 代表第 $i$ 個景點的海拔，保證所有景點的海拔高度皆不同。接下來 $M$ 行，每行有兩個相異的整數 $a\ b$（$1\le a, b\le N$），代表景點 $a\ b$ 之間有一條步道連接。
接著有一個正整數 $Q$（$1\le Q\le 500$），代表一共有 $Q$ 筆詢問，每筆詢問各有一行，該行的第一個整數 $D$（$1\le D\le 500$）代表此筆詢問使用者想去的景點數，接下來的 $D$ 個整數 $a_i$（$1\le a_i\le N$），為使用者想去的 $D$ 個景點，保證每筆詢問當中的 $D$ 個景點不重複。
對於每筆詢問，請輸出兩個整數 $t\ x$ 於一行，$t$ 代表應用程式計算出的路徑總共包含多少個使用者想去的景點，$x$ 為該路徑一共經過多少景點，兩個整數以一個空白隔開。
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
2 6
公開 測資點#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$ 分。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||