※ 引述《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)