n374. 8. 百岳健行
Tags : DP
Accepted rate : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-06-06 18:56

Content

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

  翻遍崇山峻嶺、賞盡萬千美景,生活在地貌壯麗的福爾摩沙,登山健行成了許多人休閒的項目之一。
  莊中旅行社蒐集了臺灣百岳各處知名景點的旅遊資訊,共統整了 $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\}$ 這條路徑,請輸出該路徑總共包含多少個使用者想去的景點,以及該路徑一共經過多少景點,兩個整數以一個空白隔開。

Input

  輸入的第一行有兩個正整數 $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$ 個景點不重複。

Output

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

Sample Input #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
Sample Output #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
Hint :

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

Tags:
DP
出處:
112學年度新北新莊高中校內資訊學科能力競賽 [管理者: liaoweichen1 ... (M_SQRT) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」