作者denehs (DE)
看板ACMCLUB
標題Re: [情報] NCPC 題目
時間Sun Oct 17 00:48:35 2004
※ 引述《chhsiao (bye~)》之銘言：
: ※ 引述《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
是什麼測資有錯?XD
Ghost叫我那樣寫我就直接照寫了...:P~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.240.181