岱宗夫如何?齊魯青未了。
造化鍾神秀,陰陽割昏曉。
蕩胸生曾雲,決眥入歸鳥。
會當凌絕頂,一覽眾山小。
-杜甫
翻遍崇山峻嶺、賞盡萬千美景,生活在地貌壯麗的福爾摩沙,登山健行成了許多人休閒的項目之一。
莊中旅行社蒐集了臺灣百岳各處知名景點的旅遊資訊,共統整了 $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
本題共有 $4$ 個子題,每個子題有多筆測資。
第一子題: $D=Q=1$,全部解出可得 $10$ 分。
第二子題: $D=1$,全部解出可得 $10$ 分。
第三子題: $Q=1$,全部解出可得 $10$ 分。
第四子題: 無其它限制,全部解出可得 $70$ 分。
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|