Andrew Stankevich』s Contest #2

Overview:

。第二套。。三道 DP 題。。。(A, B, E 。且都要求列印方案。。難度不是特別大。。
。(。。其中 B 題是經典的多柱河內塔問題,要考慮到以後出現各種派生的可能性。。
。。(。。好像大媽系列的所有 DP 題都要輸出方案。。。。
。兩道貪心。(。。C。 G 。然後 H 題 Polay 計數定理專門開一個頁面整理。。
。。。當然最推薦的還是 D 和 F。。

http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=1230#overview

Problem A. Non Absorbing DFA
給定一個變種的 DFA,轉移函數允許在轉移之後保留字元。
問可接受的字元串總數。
————————————————————————
求一般的自動機求可接受字元串的總數,用普通的動態規劃就可以了。
這題只要先對 NA-DFA 進行一次預處理轉換成普通 DFA 就行了。
(注意中間如果出現環則直接算做不可接受,轉移函數全部指向一個空位置即可。
高精度,自動機 dp。

Problem B. The Towers of Hanoi Revisited
給定 N 個盤子和 M 個柱子的多柱河內塔,求最少移動步數,並列印方案。
——————————————————————
設 F[m][n] 表示 m 階河內塔,n 塊盤子時移動方案的步數。則
F[m][n] = max(2 * F[m][i] + F[m-1][n-i] | 1 <= i < n) 時間複雜度 O(n^2m)。 多柱河內塔問題,動態規劃,遞歸。。。

回憶三階情況下我們的做法,每次都是將最上 n-1 個盤子,
藉助當前柱子,移動到中間柱子上,然後移動最下面的盤子到目標柱,
然後在把中間柱子上的盤子以當前柱子作為中間柱子移動到目標柱子上。。(。。。
而對於高階情況這裡的 n-1 並不一定能保證最優,只能枚舉。。(?。有規律么 。。
(另外目測隨著 M 的增加,函數值下降的會很快?。。
http://en.wikipedia.org/wiki/Tower_of_Hanoi#Multistack_Towers_of_Hanoi

Problem C. Hyperhuffman
求 Huffman Coding 的 WPL (Weighted Path Length)。。。
————————
。。直接用優先隊列 O(nlogn) 就行了,
哈夫曼樹、貪心、優先隊列

(只要求 WPL 不需要把樹實際構建出來。。
(另外輸入序列是有序的。?。

Problem D. Little Jumper
給定兩面距離為 l 的有洞的牆,洞的範圍分別為 [b1, t1] 和 [b2, t2]。
一隻諏訪子要從距離牆壁左側 ds 的地方起跳,在中間區域停頓一次,再跳到距另一面牆右側 df 遠的地方。
問至少需要多大的初速度。(不允許一跳穿過兩面牆。。
Tags:斜拋運動, math, physics, parameter search
————————
做法一:二分法 (180 ms +-。。且精度捉急。。
做法二:三分法(40 ms +-

Problem E. Quantization Problem
dp

Problem F. Roads
二分圖最小邊邊集合覆蓋

Problem G. Robbers
有 n 個強盜分 m 個金幣。第 i 個強盜的功勞是 xi。。
問如何分金幣最公平。
——————
貪心

Problem H. Toral Tickets
Polay 計數法
————————
【專題】Polay 計數定理