※ 引述《chhsiao (bye~)》之銘言： : Problem A : 一個棒球隊有 n 個投手, 要和 m 隊比賽 (m <= n <= 300), : 每位投手只能出賽一場, 而且必須完投該場球賽. : 題目給定每位投手對上每隊的勝率, 要找出最大的全勝機率. : 每位投手的勝率只有 6 種: 0, 1/5, 2/5, 3/5, 4/5, 1. : 輸入 p 代表勝率為 p/5, 輸出 a b c 代表最大全勝機率為 2^a * 3^b / 5^c. 這題是有 weight 的 bipartite matching, 我只想到 min cost max flow 的作法, 我用 adjacency matrix 做, 結果 TLE. : Problem B : 地底有許多礦坑, 而要挖某些礦坑時可能必須先挖上面的一些礦坑. : (意思就是礦坑的關係圖形成一個 directed acyclic graph) : 我們可以預先測知挖每個礦坑所獲得的利潤 (有正有負), : 題目要求我們找出能獲得的最大利潤及方法 (任何一種方法都可以). 相當有趣的一題, 目前只想到 search 解. 比賽中有想到假解法, 不過被測出有錯. 基於寫很久很辛苦的想法, 我在最後 4 分鐘寫完上一題之後還是寄寄看, 結果就...... AC 了 XD 不過事後發現 Ghost77 & 交大隊也是用其他假解法解出來的 ^^||| 不是測資沒出好，就是出題者也想錯題目了 :P --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.46 ※ 編輯: chhsiao 來自: 140.112.30.46 (10/17 00:43)