AP325 練習題解 (Ch01)

前言

最近在找題目練習時，突然想到之前連第一章都沒看完的 AP325 （講義下載），決定趁著寒假讀一下，順便做個筆記。由於例題在講義內都有滿詳細的說明，因此這裡紀錄的解法以習題為主。

Q-1-2. 合成函數(2)

這題跟 P-1-1 用一樣的方法做就好了。不過我是用 C++ 寫的，因此在 eval() 裡判斷第一個輸入是不是數字的方法不同：

int n;
if (cin >> n && cin) return n;
cin.clear();

首先嘗試進行 cin，若讀取數字失敗，則 failbit 會被設置，此時 if (cin) 會是 false，因此只有當正確讀取數字才會 return n。由於 failbit 被設置時 cin 無法正常運作，因此執行 cin.clear() 清除 failbit 才能正常執行之後的 cin。

Q-1-4. 支點切割

這題可以用前綴和 (left prefix sum) 與後綴和 (right prefix sum) 來解。

lps[i] 表示從 left 到 i 的乘積總和，rps[i] 同理。根據題目的公式，abs(rps[i] - lps[i]) 就是該切點的 cost。

以範例測資為例：

index	1	2	3	4	5
delta	0	p1	p1 + p2	p1 + p2 + p3	p1 + p2 + p3 + p4
lps[i]	0	p1	2p1 + p2	3p1 + 2p2 + p3	4p1 + 3p2 + 2p3 + p4

index	1	2	3	4	5
delta	p2 + p3 + p4 + p5	p3 + p4 + p5	p4 + p5	p5	0
rps[i]	p2 + 2p3 + 3p4 + 4p5	p3 + 2p4 + 3p5	p4 + 2p5	p5	0

然後再找出 cost 最小的 i 即為此區間的最佳切點。

Q-1-5. 二維黑白影像編碼

這題直接照著題目敘述做就好了，將字串從左到右遍歷，遇到 1 就將 res 加上 $n^2$ ，遇到 2 就進入 $n / 2$ 的遞迴。

P-1-7. 子集合乘積

這題的迴圈作法有用到 bitwise operator，<< 與 >> 分別代表左移與右移，超出範圍（例如 int 有 32 bits）的 bits 被捨棄，另一側補 0。

$n$ 個數字（包含重複）的子集合個數是 $2^n$ （需要排除空集合），每個數字分為有跟沒有兩種情況，可以用 bit 的 1 與 0 表示。例如 $n = 5$ 表示子集合個數為 25，第 11001 種情況代表此集合包含第 1、2、5 三個數字。

最後用 & 來檢查每一位是否為 1，11001 & 01000 的結果為 01000，非零表示包含第 2 個數字。

P-1-9. N-Queen 解的個數

講義中提到可以用 abs(p[i] - p[j]) == j - i 來判斷是否在對角線，此處以 4 * 4 的棋盤為例，每個數字代表第幾個皇后，- 表示空格：

-	-	2	-
-	-	-	3
0	-	-	-
-	1	-	-

由於 2 號皇后在第 0 列，3 號皇后在第 1 列，此時 p[2] = 0, p[3] = 1。套用上面的條件，可以發現兩個皇后確實在同一個對角線上，1 號與 3 號同理。

第二個遞迴解的 i = k - j + p[j] 與 i = p[j] - (k - j) 代表的意思我想了很久，其實就只是對角線的位置。以上面的棋盤為例，假設目前 k = 1, j = 0, p = [2, ?, ?, ?] （其他皇后位置未定），此時 valid = [T, T, F, T] （直線也是攻擊範圍），套用兩個算式得到 i 分別為 1, 3，頂式此兩格處於其他皇后的攻擊範圍，標記為不可放置，valid = [T, F, F, F]。

Q-1-10. 最多得分的皇后

這題可以用 P-1-9 的遞迴解，需要考慮的部分是不一定要放滿 n 個皇后，我用 -1 表示不放，最後計算分數時遇到 -1 不算該格分數（但是這個方法不夠優化）。

下面是最關鍵的部分，迴圈裡面照一般的解法，結束後追加一個 -1 表示此列不放皇后，res 用於儲存最高的分數。

for (int i = 0; i < n; i++) {
    if (valid[i]) {
        p[k] = i;
        res = max(res, nq(n, k + 1, p));
    }
}
p[k] = -1;
res = max(res, nq(n, k + 1, p));

Q-1-11. 刪除矩形邊界 — 遞迴

這題可以把矩陣設為全域變數，這樣遞迴函式只需要傳入四個邊界與 cost。直接計算四個邊各自的 cost，再縮減邊界繼續遞迴即可。如果左邊界等於右邊界，或上邊界等於下邊界，表示只剩一行或一列，此時就不用繼續往下遞迴了。