115 年 國立成功大學資訊工程系碩士班《程式設計》

核心觀念

數位搜尋樹（digital search tree）依照鍵值的位元逐層決定方向：根節點使用第 1 位，下一層使用第 2 位，依此類推。位元為 $0$ 往左子樹，位元為 $1$ 往右子樹。

插入時，從根節點開始，依照待插入鍵值各層對應的位元往下走，直到遇到空位置，便將鍵值放入該位置。搜尋時使用相同規則選擇路徑。

解題方法

鍵值依題目順序插入。第一個鍵值 000001 成為根節點。

依序插入其餘鍵值時，相關位置如下：

鍵值	插入方向（由根往下）
000010	左
000011	左 → 左
001111	左 → 左 → 右
100000	右
101011	右 → 左
111110	右 → 右

核心觀念

壓縮二元 Trie（compressed binary trie）只在「能把目前鍵值集合分成 0、1 兩組」的位元建立分支節點；所有鍵值在該位元都相同的部分會被略過。bitNumber 依題目規定從最左邊的位元開始編號，範圍為 1 到 6。

廣度優先搜尋（BFS）由根節點開始，逐層訪問分支節點；每次依序將左子節點、右子節點加入佇列。

解題方法

先找出每一組鍵值中，最左側會產生分流的位元：

• 全部七個鍵值在第 1 位分成 0 與 1，所以根節點的 bitNumber 是 1。
• 根節點左側的四個鍵值在第 1、2 位相同；第 3 位分成前三個鍵值與 001111，所以分支位元是 3。
• 000001、000010、000011 這三個鍵值在第 5 位分流；其中 000010 與 000011 再於第 6 位分流。
• 根節點右側的三個鍵值在第 2 位分成 100000、101011 與 111110；前兩個鍵值再於第 3 位分流。

因此，依層次排列的分支節點如下：

BFS 層次	由左至右的分支節點 bitNumber
第 1 層	1
第 2 層	3、2
第 3 層	5、3
第 4 層	6

依 BFS 順序串接，得到 1, 3, 2, 5, 3, 6。

建構與走訪程式碼

以下程式碼以遞迴方式找出目前鍵值集合最左側的分流位元，再以佇列依左、右順序走訪分支節點：

核心觀念

重建二元樹時：

• 後序走訪順序為「左子樹 → 右子樹 → 根節點」，因此序列最後一個鍵值是目前子樹的根。
• 中序走訪順序為「左子樹 → 根節點 → 右子樹」，因此找到根節點後，根左側與右側的鍵值分別屬於左、右子樹。

題目中的鍵值互異，所以每個根節點都能在中序序列中唯一定位。

解題方法

後序序列的最後一個鍵值是根節點 $E$。在中序序列中，以 $E$ 分開左右子樹：

• 左子樹中序：$A, C, B, D, K$
• 右子樹中序：$I, G, F, H, J$

左右子樹各有五個節點，因此對應的後序序列分別是 $A, B, C, K, D$ 與 $I, G, J, H, F$。

左子樹後序序列的最後一個鍵值是 $D$。在中序序列 $A, C, B, D, K$ 中，$D$ 左側為 $A, C, B$，右側為 $K$。其中，$A, C, B$ 的後序序列是 $A, B, C$，所以根節點是 $C$；其左右子節點分別是 $A$、$B$。

右子樹後序序列的最後一個鍵值是 $F$。在中序序列 $I, G, F, H, J$ 中，$F$ 左側為 $I, G$，右側為 $H, J$。左側子樹的根是 $G$，且 $I$ 是 $G$ 的左子節點；右側子樹的根是 $H$，且 $J$ 是 $H$ 的右子節點。

因此，重建後的樹為：

          E
        /   \
       D     F
      / \   / \
     C   K G   H
    / \   /     \
   A   B I       J

根節點 $E$ 位於第 1 層。第 2 層是 $D, F$；依此往下，第 3 層由左至右是 $C, K, G, H$。

關鍵程式碼

以下程式先依後序與中序重建樹，再以佇列依層走訪：

核心觀念

樹根在第 1 層，因此「高度」是根到最深節點所經過的節點層數。

• AVL 樹：每個節點左右子樹的高度差至多為 1。要讓節點數盡量少、同時高度盡量大，每個節點的兩個子樹高度應相差 1。
• 紅黑樹：從任一節點到其所有 NIL 葉節點的路徑，黑色節點數相同；紅色節點不能相鄰。最長路徑上的紅黑節點最多交錯排列。

解題方法

AVL 樹

令 $N(h)$ 表示高度為 $h$ 的 AVL 樹所需的最少節點數。取 $N(0)=0$、$N(1)=1$。高度為 $h$ 時，最省節點的配置是讓兩棵子樹高度分別為 $h-1$ 與 $h-2$，所以：

$$N(h)=1+N(h-1)+N(h-2)$$

依序計算：

$$N(1)=1,\quad N(2)=2,\quad N(3)=4,\quad N(4)=7,\quad N(5)=12,\quad N(6)=20$$

因為 $N(5)=12\le 15$，而 $N(6)=20>15$，所以 15 個節點的 AVL 樹高度最多為 5。

核心觀念

這段 precheck 是類似 Bloom filter（布隆過濾器） 的快速預檢。程式先把已知值 10、22 經由兩個函數映射到位元位置，並將對應位置設為 1；查詢時，只要兩個映射位置都為 1，就通過預檢，才進一步執行 exact_check。

布隆過濾器式的預檢可能發生假陽性：不在集合中的值，也可能因為映射到已被設為 1 的位置而通過。通過預檢不代表該值一定等於 10 或 22。

解題方法

先計算 base 中兩個值對應的位元位置：

值	$f1(x)=x\bmod 8$	$f2(x)=\lfloor x/2\rfloor\bmod 8$
$10$	$2$	$5$
$22$	$6$	$3$

因此，位元位置 $2, 3, 5, 6$ 會被設為 1。查詢時，precheck 要求 f1(x) 和 f2(x) 對應的位置同時為 1，也就是以邏輯 AND 串接兩個檢查。

例如，$x=11$ 時，$f1(11)=3$、$f2(11)=5$，兩個位置都已設為 1，所以預檢會通過；但 exact_check(11) 為假。

核心觀念

程式先用位元集合做快速預檢，再對通過預檢的輸入執行精確檢查：

• f1(x) = x % 8
• f2(x) = (x / 2) % 8，此處 x 為非負整數，整數除法會捨去小數部分。
• precheck 只有在位元位置 f1(x) 和 f2(x) 都已設為 1 時才通過。
• exact_checks 計算通過預檢的輸入數；blocked 則計算其中等於 10 或 22 的輸入數。

解題方法

先依序算出基準值 {10, 22} 設定的位元位置：

基準值	f1(x)	f2(x)
10	$10 \bmod 8 = 2$	$(10 / 2) \bmod 8 = 5$
22	$22 \bmod 8 = 6$	$(22 / 2) \bmod 8 = 3$

因此，位元集合中設為 1 的位置是 $\{2, 3, 5, 6\}$。

接著逐一計算輸入：

輸入 x	f1(x)	f2(x)	預檢結果	精確檢查結果
10	2	5	通過	等於 10，封鎖
14	6	7	不通過	不執行

核心觀念

precheck 是快速篩選：它會檢查 $x$ 的兩個索引位置是否都已在位元集合 bits 中。只有通過快速篩選的 $x$，才會進一步執行 exact_check。

本題的索引函式為：

$$f_1(x)=x\bmod 8,\qquad f_2(x)=\left\lfloor\frac{x}{2}\right\rfloor\bmod 8$$

位元集合透過 1u << p 設定第 $p$ 個位元；get1(bits, p) 則檢查該位元是否為 $1$。

解題方法

先計算 base = {10, 22} 對應的位元索引：

$x$	$f_1(x)$	$f_2(x)$
10	$10\bmod 8=2$	$\lfloor10/2\rfloor\bmod 8=5$
22	$22\bmod 8=6$	$\lfloor22/2\rfloor\bmod 8=3$

因此，bits 中設為 $1$ 的位置是 $\{2,3,5,6\}$。通過快速篩選的條件為：

$$f_1(x)\in\{2,3,5,6\} \quad\text{且}\quad f_2(x)\in\{2,3,5,6\}$$

依非負整數由小到大檢查：

$x$	$f_1(x)$	$f_2(x)$	通過 precheck？
0	0	0	否
1	1	0	否
2	2	1	否
3	3	1	否
4	4	2	否
5	5	2	是

核心觀念

precheck 是快速篩選：它用兩個雜湊函數，把黑名單中的數字映射到 bits 的位元位置。只有兩個位置都為 $1$，程式才會執行 exact_check 做精確比對。

因此，base 負責建立快速篩選所需的位元集合，exact_check 則負責判斷輸入是否真的屬於黑名單。更新黑名單時，這兩處都必須反映新增的數字；precheck 的雜湊與篩選邏輯不必改動。

解題方法

新黑名單為 $\{10,14,22\}$。計算各數字的雜湊位置：

數字 $x$	$f_1(x)=x\bmod 8$	$f_2(x)=\lfloor x/2\rfloor\bmod 8$
10	2	5
14	6	7
22	6	3

原本 base 只有 {10, 22}，建立的位元集合包含位置 $2,5,6,3$，沒有包含位置 $7$。所以輸入 $14$ 會在 precheck 被擋下，無法進入精確檢查。必須把 14 加入 base，讓快速篩選設定位元 $6$ 與 $7$。

同時，exact_check 也必須加入對 $14$ 的判斷，否則即使 $14$ 通過快速篩選，精確檢查仍不會將它判定為黑名單成員。

關鍵程式碼應更新為：

int base[] = {10, 14, 22};

static int exact_check(int x) {
    return (x == 10) || (x == 14) || (x == 22);
}

核心觀念

本題考的是 Kruskal 最小生成樹演算法。把校園建築視為頂點、光纖連線視為帶權無向邊，目標是在連通所有建築的前提下，使總施工成本最低。

Kruskal 的做法是依邊權由小到大考慮每條邊；只有當邊的兩端目前屬於不同連通分量時，才加入答案。這樣可避免形成環。程式使用並查集維護連通分量：

• f1(x)：找出頂點 $x$ 所屬集合的代表，並透過路徑壓縮加速。
• f2(x, y)：若兩端代表不同，就合併集合並回傳 1；否則代表加入此邊會形成環，回傳 0。合併時依集合大小合併。

解題方法

程式先將每條邊的端點調整成 $a \le b$，再依照 (w, a, b) 排序。如此一來，邊權相同時，會依題目指定的端點順序排列。

接著逐邊掃描排序結果：

1. 呼叫 f2(a, b) 檢查兩端是否屬於不同集合。
2. 若不同，加入該邊、累加成本，並增加已選邊數 k。
3. 選到 $n-1$ 條邊時停止；若圖連通，這些邊便構成最小生成樹。

程式的關鍵部分如下：

for (int i = 0; i < m && k < n - 1; i++) {
    if (f2(e[i].a, e[i].b)) {
        total += e[i].w;
        k++;
    }
}

核心觀念

程式使用 Kruskal 演算法求最小生成樹：先將邊依照權重由小到大排序，再依序加入不會形成環的邊，直到選出 $n-1$ 條邊，或所有邊都處理完畢。

程式以並查集判斷兩個端點是否已在同一連通分量：

• f1(x)：尋找頂點 $x$ 所屬集合的代表元。
• f2(x, y)：若兩端點分屬不同集合，就合併並回傳 1；若已在同一集合，代表加入此邊會形成環，回傳 0。

輸出格式為「選取邊的總權重」與「選取邊數」。

解題方法

將輸入邊依權重由小到大排序：

權重	邊	處理結果
1	$(3,5)$	選取
2	$(1,4)$	選取
3	$(0,2)$	選取
4	$(0,1)$	選取
5	$(1,2)$	略過，會形成環
6	$(0,3)$	選取

加入權重為 $1、2、3、4$ 的邊後，頂點 $0、1、2、4$ 已連成一個分量；頂點 $3、5$ 則由邊 $(3,5)$ 連成另一個分量。此時邊 $(1,2)$ 的兩端已在同一分量，加入會形成環，因此略過。

接著選取權重為 $6$ 的邊 $(0,3)$，將兩個分量連接起來。此時共有 $n-1=5$ 條邊，迴圈停止。

$$\text{總權重}=1+2+3+4+6=16$$

選取邊數為 $5$，程式輸出：

核心觀念

關節點（articulation point）：移除該頂點及其相連的邊後，圖的連通分量會增加。若圖是一棵樹，每條邊都是橋，因此：

$$\text{樹中的頂點是關節點} \iff \text{它的度數} \ge 2 .$$

（葉節點度數為 1，拿掉不會把其他頂點分開；度數至少 2 的頂點拿掉後，它的各個鄰居會落在不同分量。）

解題方法

第 6 題的資料集經 Kruskal 選出的骨幹邊（依加入順序）：

權重	邊
1	$(3,5)$
2	$(1,4)$
3	$(0,2)$
4	$(0,1)$
6	$(0,3)$

（權重 5 的 $(1,2)$ 因會成環被略過。）共 $5=n-1$ 條邊，骨幹是一棵含 6 個頂點的樹：

      2
      |
4 — 1 — 0 — 3 — 5

各頂點在骨幹中的度數：

核心觀念

題目考查並查集（Disjoint Set Union, DSU）如何表示圖的連通分量。每個集合代表一個連通分量，集合的根節點滿足 P[root] == root。因此，並查集中根節點的數量就是連通分量數。

解題方法

Kruskal 程式只在選出 $n-1$ 條邊時停止。若已選出 $n-1$ 條邊，圖已連通，連通分量數為 $1$；若尚未選足 $n-1$ 條邊，迴圈會掃完所有輸入邊。兩種情況下，迴圈結束時 DSU 的集合都對應輸入圖的連通分量。

因此，可以用 f1(i) == i 計算根節點，也可以直接用 P[i] == i 計算根節點。兩種寫法都正確：

int c = 0;
for(int i=0;i<n;i++){
    if(f1(i) == i) c++;
}
printf("%lld %d %d\n", total, k, c);

或：

int c = 0;
for(int i=0;i<n;i++){
    c += (P[i] == i);
}
printf("%lld %d %d\n", total, k, c);

選項分析

核心觀念

前驅與後繼是有序集合中的查詢：

• $x$ 的前驅：集合中小於 $x$ 的最大鍵值。
• $x$ 的後繼：集合中大於 $x$ 的最小鍵值。

判斷資料結構能否有效支援這類查詢，關鍵在於它是否保留鍵值順序，以及從根節點找到 $x$ 所需的時間。紅黑樹與 AVL 樹都是高度為 $O(\log n)$ 的平衡搜尋樹，因此能在 $O(\log n)$ 最壞時間內搜尋並定位前驅或後繼。

解題方法

從根節點搜尋 $x$ 時，可以同時記錄候選答案。以尋找後繼為例：走到鍵值大於 $x$ 的節點時，該節點是候選後繼，接著往左找更小但仍大於 $x$ 的鍵值；走到小於 $x$ 的節點時，往右找。前驅則對稱處理。

successor(root, x):
    candidate = NONE
    node = root

    while node != NONE:
        if node.key > x:
            candidate = node.key
            node = node.left
        else:
            node = node.right

    return candidate

核心觀念

本題比較三種優先佇列結構的操作效率：

• Fibonacci heap：擅長合併與刪除最小值。合併的攤銷時間為 $O(1)$，刪除最小值的攤銷時間為 $O(\log n)$。
• Leftist heap（左偏樹）：透過左偏性質限制右路徑長度，使合併與刪除最小值都能在 $O(\log n)$ 時間內完成。
• SMMH（Symmetric Min-Max Heap，對稱最小最大堆）：同時維持最小值與最大值的結構，能在 $O(1)$ 時間取得兩端的極值。

其中，Fibonacci heap 與 leftist heap 通常是最小堆，只有最小值位於堆頂；若沒有額外結構，不能直接以 $O(1)$ 取得最大值。

解題方法

逐項對照各結構的支援操作與時間複雜度。題目要求頻繁合併與刪除最小值，因此合併和 delete-min 都有效率的結構符合需求；偶爾查詢最大值則不代表最小堆能直接提供 $O(1)$ 的 find-max。

選項分析

核心觀念

這題考的是磁碟索引的設計：磁碟讀取通常以「頁」或「區塊」為單位，因此索引節點能在一頁中存放越多鍵值與子節點指標，樹的分支度（fan-out）就越高，搜尋時需要讀取的頁數通常越少。

若每個內部節點最多有 $f$ 個子節點，索引含有 $N$ 筆資料，樹高大致與下式同階：

$$h = O(\log_f N)$$

在磁碟索引中，搜尋路徑上的每一層通常都需要讀取一頁。$f$ 越大，$h$ 越小，搜尋所需的頁面讀取次數也越少。

解題方法

逐項判斷各種樹的節點容量與高度：

• B-tree 與 B+ tree 的節點可在一頁中存放多個鍵值及子節點指標，因而具有高分支度。
• 紅黑樹是二元搜尋樹，每個節點最多只有兩個子節點。若每個節點各自存於一頁，搜尋路徑會比高分支度的樹更長。
• B+ tree 的葉節點常以指標串接，適合依序掃描相鄰鍵值，對範圍查詢尤其有利。

選項分析

(A) 正確。
B-tree 的節點能在一個磁碟頁或區塊中存放多個鍵值與子節點指標，因此分支度高。搜尋時只需讀取少數層級的頁面，適合磁碟索引。

核心觀念

大 $O$ 表示漸近上界。若存在常數 $c>0$ 與 $n_0$，使得對所有 $n\ge n_0$ 都有

$$T(n)\le c n^2,$$

就能宣稱 $T(n)=O(n^2)$。

判斷時，固定常數項不影響漸近成長階；若每一項都能被 $n^2$ 的常數倍所界定，整個函數也能被 $n^2$ 的常數倍所界定。

解題方法

取 $n\ge 2$。對常見的對數底數，$\log n\le n$，因此

$$200n\log n\le 200n^2.$$

此外，$n\ge 2$ 時 $n^2\ge 1$，所以

$$10^6\le 10^6n^2.$$

合併各項：

核心觀念

本題考「NP-hard」與「NP-complete」的差別：

• NP-hard（NP 困難）：每個屬於 NP 的問題，都能在多項式時間內歸約到此問題。NP-hard 問題本身不必屬於 NP，也不必可判定。
• NP-complete（NP 完全）：問題必須同時是 NP-hard，且屬於 NP。

因此：

$$\mathrm{NP\text{-}Complete}=\mathrm{NP\text{-}Hard}\cap\mathrm{NP}$$

屬於 NP 的問題都能由多項式時間驗證器在有限時間內驗證，因而是可判定的。停機問題已知不可判定，所以不屬於 NP。

解題方法

判斷題目中的推論是否成立，關鍵是檢查它是否漏掉 NP-complete 的必要條件。

核心觀念

本題考查複雜度類別 NP 的定義。對於一個判定問題，若輸入答案為「是」，存在一份長度受輸入大小多項式限制的證明（也稱候選解或憑證），且可由確定性演算法在多項式時間內驗證，就可用「多項式時間驗證器」描述該問題屬於 NP。

形式上，判定問題 $L$ 屬於 NP，表示存在確定性多項式時間驗證器 $V$，使得對輸入 $x$：

$$x \in L \iff \exists y,\ |y| \leq \operatorname{poly}(|x|),\ V(x,y)=1$$

其中 $y$ 是候選解，$V(x,y)=1$ 表示驗證器確認候選解有效。

解題方法

核心觀念

0/1 背包問題中，每件物品只能「整件選取」或「完全不選」，不能拆分。若物品 $i$ 的重量為 $w_i$、價值為 $v_i$，背包容量為 $W$，目標是在總重量不超過 $W$ 的條件下，最大化總價值。

依「價值重量比」$v_i/w_i$ 由高至低選取，是分數背包問題的最佳貪婪策略；在 0/1 背包中，物品不能拆分，這項策略不保證得到最佳解。

解題方法

用反例檢驗題目所稱的策略是否對所有輸入都能得到最佳解。設背包容量為 $50$，有以下三件物品：

物品	重量	價值	價值重量比
1	10	60	6
2	20	100	5
3	30	120	4

核心觀念

要證明問題 $B$ 是 NP-Complete，須證明兩件事：

1. $B \in NP$：給定一個候選解，可以在多項式時間內驗證它是否正確。
2. $B$ 是 NP-hard：將一個已知的 NP-Complete 問題 $A$ 多項式時間歸約到 $B$，也就是證明 $A \le_p B$。

歸約方向的意義是：若能在多項式時間內解決 $B$，便能藉由轉換後的實例，在多項式時間內解決 $A$。因此，$A$ 至少和 $B$ 一樣難。

解題方法

令 $A$ 為已知 NP-Complete 的 Robot-Path-Planning，目標 $B$ 為 3-SAT。要證明 3-SAT 是 NP-Complete，應證明：

$$\text{3-SAT} \in \text{NP}$$

並構造多項式時間歸約：

$$\text{Robot-Path-Planning} \le_p \text{3-SAT}$$

題幹要求的歸約方向是：

核心觀念

使用 $\Theta$ 記號分析時間複雜度時，要計算輸入規模 $n$ 增加時，基本操作執行次數的漸近成長率。常數倍不影響 $\Theta$ 階。

解題方法

Surface_Scan(n) 有兩層迴圈：

核心觀念

遞迴式由兩部分組成：每次呼叫自身所需的非遞迴工作，以及遞迴子問題的數量與大小。MRI_Voxel_Process(n) 在每個非基本情況中，會呼叫 8 次規模為 $n/2$ 的子問題。

解題方法

先計算每次 Surface_Scan(n) 的工作量。外層迴圈執行 $n$ 次，內層迴圈固定執行 100 次；每次 Read_Pixel 為常數時間，因此一次掃描耗時 $\Theta(100n)=\Theta(n)$。

MRI_Voxel_Process(n) 會執行 $n$ 次掃描，所以非遞迴工作量為：

$$n \cdot \Theta(n)=\Theta(n^2)$$

接著計算遞迴工作：三層迴圈分別讓 $x,y,z$ 取 0 或 1，共產生 $2 \times 2 \times 2=8$ 個子問題，每個子問題的規模都是 $n/2$。

因此，當 $n>1$ 時：

核心觀念

本題考察遞迴時間複雜度。先計算每次遞迴呼叫中「非遞迴工作」的成本，再建立遞迴式，最後使用主定理求出漸近緊確界。

解題方法

在 Surface_Scan(n) 中，外層迴圈執行 $n$ 次，內層迴圈固定執行 $100$ 次；每次 Read_Pixel(i, j) 為常數時間。因此：

$$T_{\text{Surface\_Scan}}(n) = n \cdot 100 \cdot \Theta(1) = \Theta(n)$$

MRI_Voxel_Process(n) 會呼叫 Surface_Scan(n) 共 $n$ 次，所以這部分的成本為：

$$n \cdot \Theta(n) = \Theta(n^2)$$

接著，三層從 $0$ 到 $1$ 的迴圈各產生 $2$ 次執行，合計呼叫 $2 \cdot 2 \cdot 2 = 8$ 次規模為 $n/2$ 的子問題。因此遞迴式為：

$$T(n) = 8T\left(\frac{n}{2}\right) + \Theta(n^2)$$

且 $T(1) = \Theta(1)$。

使用主定理，$a=8$、$b=2$、$f(n)=\Theta(n^2)$，並計算：

核心觀念

這題是「加權非相鄰選取」問題：每個班次有一個產值，選取的班次不能相鄰，目標是讓總產值最大。這等價於在路徑圖上找最大權重獨立集，也可用一維動態規劃求解。

令 $dp[i]$ 表示只考慮 $S1$ 到 $Si$ 時，符合限制的最大總產值。對第 $i$ 個班次只有兩種決策：

• 不選 $Si$：最大值為 $dp[i-1]$。
• 選 $Si$：因為 $S_{i-1}$ 必須休息，最大值為 $dp[i-2]+v_i$。

因此遞迴式為：

$$dp[i]=\max\bigl(dp[i-1],\ dp[i-2]+v_i\bigr)$$

邊界條件為 $dp[0]=0$，且 $dp[1]=v_1$。

解題方法

依照上式逐班次計算：

班次 $i$	產值 $v_i$	$dp[i]$	最佳決策
1	45	45	選 $S1$
2	95	95	選 $S2$
3	45	95	不選 $S3$
4	35	130	選 $S4$
5	85	180	選 $S5$
6	45	180	不選 $S6$
7	40	220	選 $S7$
8	85	265	選 $S8$
9	65	285	選 $S9$
10	65	330	選 $S10$
11	40	330	不選 $S11$
12	35	365	選 $S12$
13	90	420	選 $S13$

計算幾個關鍵步驟如下：

$$dp[4]=\max(95,\ 95+35)=130$$ $$dp[8]=\max(220,\ 180+85)=265$$ $$dp[10]=\max(285,\ 265+65)=330$$ $$dp[13]=\max(365,\ 330+90)=420$$

最大總產值為 $dp[13]=420$。接著從 $S13$ 往回追蹤：選 $S13$ 後退兩格至 $dp[11]$；$S11$ 不選，改取 $dp[10]$；選 $S10$ 後退至 $dp[8]$；選 $S8$ 後退至 $dp[6]$；$S6$ 不選，取 $dp[5]$；選 $S5$ 後退至 $dp[3]$；$S3$ 不選，取 $dp[2]$，選 $S2$。

所以選取的班次為 $S2、S5、S8、S10、S13$，總值為：

核心觀念

這題是「路徑圖上的最大權重獨立集」問題：每個班次是一個節點，價值是節點權重，相鄰班次不能同時選取。題目另外要求必須選擇 S7。

固定 S7 後，S6、S8 必須停機，因此其餘可選班次分成兩段：S1～S5 與 S9～S13。兩段彼此不影響，可以各自求最大值，再加上 S7 的價值。

解題方法

對一段班次定義 $DP[i]$ 為前 $i$ 個班次在不選相鄰班次時的最大總價值。處理第 $i$ 個班次時，只有兩種情況：

• 不選第 $i$ 個：沿用 $DP[i-1]$。
• 選第 $i$ 個：第 $i-1$ 個不能選，因此價值為 $v_i+DP[i-2]$。

所以遞迴式為：

$$DP[i]=\max(DP[i-1],\ v_i+DP[i-2])$$

左段：S1～S5

價值依序為 $45,95,45,35,85$。逐步套用遞迴式：

班次範圍	最大總價值
S1	45
S1～S2	95
S1～S3	95
S1～S4	130
S1～S5	180

左段選 S2、S5，總價值為 $95+85=180$。

右段：S9～S13

價值依序為 $65,65,40,35,90$。套用相同遞迴式：

班次範圍	最大總價值
S9	65
S9～S10	65
S9～S11	105
S9～S12	105
S9～S13	195

右段選 S9、S11、S13，總價值為 $65+40+90=195$。

加上必選 S7 的價值 $40$：

$$180+40+195=415$$

關鍵程式碼

核心觀念

這題考的是「帶有間隔限制的最大值選擇」動態規劃。每個班次只有兩種決策：安排第 $i$ 班，或讓第 $i$ 班休息。

若安排第 $i$ 班，機器必須接著休息兩班，因此第 $i-1$、$i-2$ 班都不能安排生產；前面最多只能接到第 $i-3$ 班的最佳排程。

解題方法

不安排第 $i$ 班時，最佳值是 $f[i-1]$。安排第 $i$ 班時，取得價值 $v_i$，並加上截至第 $i-3$ 班的最佳值 $f[i-3]$。取兩種情況的較大者：

$$f[i]=\max\bigl(f[i-1],\ f[i-3]+v_i\bigr)$$

邊界可設為 $f[0]=f[1]=f[2]=0$；對 $i=1,2$，安排當前班次時，前面可接的最佳值視為 $0$。這題不是選擇題，因此沒有選項需要逐一分析。

關鍵程式碼與複雜度

核心觀念

需求是「分析整個網路的延遲特性，讓任兩顆衛星之間的最短通訊路徑在需要時能立即查到」——這是全點對最短路徑（all-pairs shortest paths）問題，而且圖中有負權重邊 $A\to C=-5$。

解題方法

1. 檢查負權重環：圖中的有向環

   • $A\to C\to B\to D\to A$：$-5+4+5+3=7$
   • $A\to B\to D\to A$：$10+5+3=18$
   • $C\to B\to D\to C$：$4+5+2=11$

   都是正的，沒有負權重環，最短路徑有明確的有限值。

2. 選擇演算法：Floyd–Warshall 以距離矩陣為基礎，逐一允許每個節點 $k$ 當中繼點：

   $$d[i][j]\leftarrow\min\bigl(d[i][j],\ d[i][k]+d[k][j]\bigr)$$

   它允許負權重邊（只要沒有負權重環），一次算出所有節點對的最短距離，之後任何查詢都是查表 $O(1)$，正好符合「需要時能有效率地取得」。時間 $\Theta(V^3)$、空間 $\Theta(V^2)$；$V=4$ 時計算量極小。

核心觀念

這題考的是以 Floyd–Warshall 演算法求所有節點對之最短路徑時，如何建立初始距離矩陣。矩陣中的 $M[i][j]$ 表示節點 $i$ 到節點 $j$ 的直接邊權重；若沒有直接邊，設為 $\infty$；自己到自己的距離設為 $0$。

解題方法

依照題目指定的節點順序 A、B、C、D，將每條有向邊填入對應的「起點列、終點欄」：

• A → B 為 $10$，A → C 為 $-5$
• B → D 為 $5$
• C → B 為 $4$
• D → A 為 $3$，D → C 為 $2$

其餘非對角線位置沒有直接邊，填入 $\infty$；對角線位置填入 $0$。因此：

$$M= \begin{bmatrix} 0 & 10 & -5 & \infty\\ \infty & 0 & \infty & 5\\ \infty & 4 & 0 & \infty\\ 3 & \infty & 2 & 0 \end{bmatrix}$$

Floyd–Warshall 後續會依序嘗試以每個節點 $k$ 作為中繼點，更新距離：

核心觀念

本題要求節點 $D$ 到節點 $B$ 的最短路徑成本。依四個節點的全點對最短路徑情境，使用 Floyd–Warshall 演算法：逐一允許節點作為中繼點，更新任意兩點間的距離。

更新公式為：

$$d[i][j] = \min\bigl(d[i][j],\ d[i][k] + d[k][j]\bigr)$$

其中 $k$ 是目前允許作為中繼點的節點。

解題方法與計算

初始距離設為：對角線 $d[i][i]=0$、有直接邊的距離設為邊權重，其餘設為無限大。

考慮經過 $A$ 的路徑：

$$D \to A \to C = 3 + (-5) = -2$$

因此，$D$ 到 $C$ 的成本可更新為 $-2$。接著考慮經過 $C$ 到達 $B$：

$$D \to C \to B = -2 + 4 = 2$$

對應的完整路徑是：

$$D \to A \to C \to B$$

其成本為 $3 + (-5) + 4 = 2$。另一條直接可見的路徑 $D \to C \to B$ 成本為 $2+4=6$，因此不如經過 $A$ 的路徑。

關鍵程式碼與複雜度

核心觀念

本題組選用的演算法是 Floyd–Warshall（全點對最短路徑、可處理負權重邊）。它的時間複雜度由三層迴圈決定：

for k = 1 to V
    for i = 1 to V
        for j = 1 to V
            d[i][j] = min(d[i][j], d[i][k] + d[k][j])

解題方法

核心觀念

這題考的是「局部貪婪選擇」：每一步只查看能讓游標更接近目標的相鄰格，選擇進入能量成本最低的格子，不會預先規劃整條路徑。

此處「更接近」以曼哈頓距離衡量。座標 $(r,c)$ 到目標 $(r_T,c_T)$ 的曼哈頓距離為

$$|r-r_T|+|c-c_T|$$

每次移動都必須讓此距離減少 $1$。路徑成本則是沿途進入的像素成本總和；起點 $S$ 不計，目標 $T$ 的成本為 $0$。

解題方法

目標座標是 $(3,4)$。從目前位置列出能縮短曼哈頓距離的鄰格，選其中能量成本最低者；若成本相同，依序使用右、下、上、左的優先順序。

目前位置	能縮短距離的候選格（進入成本）	選擇
$(0,0)$	右 $(0,1)$：$4$；下 $(1,0)$：$7$	$(0,1)$
$(0,1)$	右 $(0,2)$：$5$；下 $(1,1)$：$9$	$(0,2)$
$(0,2)$	右 $(0,3)$：$9$；下 $(1,2)$：$8$	$(1,2)$
$(1,2)$	右 $(1,3)$：$6$；下 $(2,2)$：$4$	$(2,2)$
$(2,2)$	右 $(2,3)$：$1$；下 $(3,2)$：$6$	$(2,3)$
$(2,3)$	右 $(2,4)$：$5$；下 $(3,3)$：$7$	$(2,4)$
$(2,4)$	下 $(3,4)=T$：$0$	$(3,4)$

因此路徑為

$$(0,0)\rightarrow(0,1)\rightarrow(0,2)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(2,4)\rightarrow(3,4)$$

起點不計入成本，將其餘各格的成本相加：

$$4+5+8+4+1+5+0=27$$

關鍵程式碼

核心觀念

本題要求在所有合法路徑中，找出進入像素能量成本總和最小的路徑。這是非負權重圖的單源最短路徑問題，適合使用 Dijkstra 演算法。

把每個像素視為圖上的頂點；從像素 $u$ 移動到相鄰像素 $v$ 的邊權重，設為「進入 $v$ 的成本」。因此，起點 $S$ 的成本不計，將起點距離設為 $0$；目標像素 $T$ 的成本為 $0$，照常納入路徑。

解題方法

從 $S=(0,0)$ 開始，逐步取出目前累積成本最小的像素，並嘗試更新它的上下左右鄰居。方向依題目指定順序設定為右、下、上、左。對每個鄰居 $v$，候選成本為：

$$\operatorname{dist}(u)+\operatorname{cost}(v)$$

沿最短路徑的關鍵累積成本如下：

像素	進入該像素的成本	累積成本
$(0,0)$	起點不計	$0$
$(1,0)$	$7$	$7$
$(2,0)$	$3$	$10$
$(2,1)$	$2$	$12$
$(2,2)$	$4$	$16$
$(2,3)$	$1$	$17$
$(2,4)$	$5$	$22$
$(3,4)=T$	$0$	$22$

因此，最短路徑是沿左側往下，再沿第 2 列向右，最後進入目標像素。

關鍵程式碼與複雜度

以下程式以優先佇列實作 Dijkstra；方向陣列依「右、下、上、左」排列。

核心觀念

優先佇列的 Extract-Min 操作，是取出目前累積成本最小的候選像素。時間複雜度取決於資料結構如何維持與尋找最小值。

以下以目前優先佇列中的候選像素數量 $k$ 分析；$k$ 最多可達影像像素總數 $N$。

解題方法

Case 1：未排序陣列

陣列沒有依成本排序，因此必須逐一比較 $k$ 個候選像素，才能確定最小值。比較需要 $O(k)$ 時間；找到最小值後，用最後一個元素補上空位即可在 $O(1)$ 時間完成移除。

extractMin(array):
    minIndex = 0
    for i = 1 to array.length - 1:
        if array[i].cost < array[minIndex].cost:
            minIndex = i
    minPixel = array[minIndex]
    array[minIndex] = array[array.length - 1]
    removeLast(array)
    return minPixel

掃描成本主導整體時間，因此 Extract-Min 為 $O(k)$。若以 $N$ 表示候選像素數量上限，最壞情況為 $O(N)$。