題目敘述 : https://drive.google.com/file/d/1nDZNGCptQGcAZDxqRGcNt_wpz31clODZ/view?usp=sharing
許多遊戲的設計是以關卡為單位,玩家通過一個關卡後才能挑戰下一個關卡。這些關卡的解鎖關係有時並不是線性的,也就是玩家通過一個關卡後可能一次開放多個可以挑戰的新關卡,也可能不會開放任何新關卡。
經典的A遊戲就屬於這種非線性的關卡結構。關卡的狀態分為三種:「尚未解鎖」、「已解鎖但未通過」以及「已通過」。A遊戲有 $n$ 個關卡,被呈現在一張地圖上,其中有 $m$ 對關卡存在相互解鎖關係,以 $(u_i, v_i)$ 表示。當玩家通過關卡 $u_i$ 時,關卡 $v_i$ 將被解鎖;反過來說,當玩家通過關卡 $v_i$ 時,關卡 $u_i$ 也會被解鎖。玩家可以從任意關卡開始遊戲,且保證在非線性的玩法下,可以通過其他所有關卡。另,為了避免破關流程過於簡單,A遊戲滿足 $m ≤ n$ 。
凱特決定把A遊戲當作線性解鎖關卡來玩:選擇一個起始關卡,接著一旦通過了某個關卡 $c$ 後,下一關只能是與關卡 $c$ 有相互解鎖關係的關卡,且一關最多只能通過一次。已知凱特通過關卡 $i$ 時,得到的成就感為 $a_i$,請幫他找出最適合的破關路徑以最大化成就感總和。
舉例來說,假設A遊戲的關卡地圖如下圖所示,圖中圓點中的數字代表關卡編號,圓點旁邊的數字代表該關卡破關所得到的成就感;兩個關卡的連線代表一個相互解鎖關係。若凱特選擇從關卡 $7$ 開始破關,則關卡 $5$ 將被解鎖,接著依序通過關卡 $5, 1, 3, 6, 2$,得到的成就感總和為 $4 + (−3) + (−1) + 3 + 0 + 2 = 5$。另一方面,若凱特選擇從關卡 $8$ 開始破關,並依序通過關卡 $6, 3, 1, 2$,得到的成就感總合為 $2 + 0 + 3 + (−1) + 2 = 6$,此時成就感總和為最大值。
• $1 ≤ n ≤ 10^5$。
• $m = n − 1$ 或 $m = n$。
• $1 ≤ u_i < v_i ≤ n$,且若 $i \ne j$,保證 $(u_i, v_i) \ne (u_j , v_j )$。
• $-10^9 ≤ a_i ≤ 10^9$。
• 遊戲設計保證正常遊玩(非線性)時從任何一關做為起始關卡皆能解鎖所有關卡。
• 上述變數都是整數。
$n$ $m$ $u_1$ $v_1$ $u_2$ $v_2$ ... $u_m$ $v_m$ $a_1$ $a_2$ . . . $a_n$ |
• $n$ 代表關卡數。
• $m$ 代表解鎖關係數。
• $u_i, v_i$ 代表通過關卡 $u_i$ 或 $v_i$ 的其中一個後,另一個關卡將被解鎖。
• $a_i$ 代表凱特通過關卡 $i$ 時的成就感。
$s$ |
• $s$ 為一整數,代表凱特能獲得的最大成就感總和。
8 8 6 8 3 6 2 6 1 3 1 2 1 4 1 5 5 7 -1 2 3 -10 -3 0 4 2
6
2 1 1 2 -1 -10
-1
題目和測資來源 : twpca
注意因為礙於系統問題測試資料沒辦法完整的放上來,所以也許會有測資不夠強的狀況,歡迎提出。
子任務 | 分數 | 額外輸入限制 | 測資點 |
1 | 17 | $n ≤ 100$ | #00~#05 |
2 | 23 | $m = n − 1$ | #06~#09 |
3 | 34 | $a_i ≥ 0$ | #10~#16 |
4 | 26 | 無額外限制 | #17~#19 |
如果題目有問題歡迎來信詢問!
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
39475 | asdfasdfasdf ... (unknown) | k186 | 193 | 2024-02-25 21:29 |