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