ZOJ 3282 Go Downstairs

ZOJ 12月月賽題目。

給出每行有及僅有一個梯級，有或沒有金幣，幣值。每一行的梯級必然在上一行的梯級的左方或右方。一個在這張圖上的遊戲是這樣的﹕首玩者可以以費用選擇移去該行的梯級，麼次玩者會垂直掉到最接近的梯級，或離開地圖。如果該梯級有金幣的話也一併移掉。次玩者可以選擇修復剛移除的梯級(最多只能操作次)，但不能修復原有的金幣。每當他走到有金幣的話他必定會取走。次玩者必然從最頂層出發。首玩者先操作。當次玩者跳離地圖，遊戲便結束。

問，若果金幣全屬首玩家所有，那麼在雙方採取最優策略底下，首玩家的損失最小是甚麼。

首先，不難留意這張圖可以化為有向無環圖。頂層梯級為出發點，並構造虛擬終點(即跳離地圖的狀態)。然後可以結論這道題目是Minimax題。簡單的動態規劃可以搞定。狀態為，當中是行數、是用了多少次修復，為玩者編號。轉移方程也很一般，不贅述。

此題唯一比較不足的地方是，應該容許兩層梯級可以共處同一垂直位置，而且應該考慮同一梯級可以重覆修復及移除。但是題目實際上如果移除了，某人就必須走下一級。這樣，下列的情況會得出不一樣的答案﹕

5 5 5 1 2
G....
G....
G....
G....
G....

(注意根據原題描述，此情況絕不會發生)

USACO Cow Pedigrees

給定N和K，問有多少棵高度為K、N個頂點的二叉樹。對二叉樹的要求是除葉子外所有頂點必須有兩個子節點。

明明是很簡單的動態規劃，卻搞了我很多時間…

定義目標函數 F[N][K] 即題目要求數。

觀察﹕
(1) F[N][K]必須依賴 F[i][K-1]，使得二叉樹數符合要求。
(2) 必須分配單數子節點予任意子樹，否則必得無乎合要求的二叉樹。
(3) 得出轉移方程為 F[i][K-1] * F[N-1-i][j] * 2 的總和，當中 j < K-1。
(4) 另需加上F[i][K-1] * F[N-i-1][K-1]，因為交換子樹視同相等。
(5) 合法狀態必須符合 2*K < N + 2，因為一棵符合要求的子樹至少是Left Completed，必然有2 * K - 1點，否則無法構建二叉樹。

沒有留意(5)便會造成很多無謂的錯誤。

ICPC2556 Four Quarters

題目給出玩者間的得失矩陣，說明兩位玩者各擲錢幣兩次後對應的得失情況，並問第1至20回合間的勝負比率。

這是一道頗簡單的動態規劃題。

假定為在第回合，玩者的得分減去玩者的得分為的概率。
轉移方程便是

當中及便是兩位玩者的分數，代表發生結果的概率。比如。
撇除輸出，這是一道經典的題目。