看板ACMCLUB
标 题Re: [请益] 好题目q:
发信站批踢踢兔 (Fri Jul 7 14:27:52 2006)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ 引述《pp5438 (厄阿)》之铭言：
: ※ [本文转录自 hil 看板]
: 作者: pp5438 (厄阿) 看板: hil
: 标题: [请益] 好题目q:
: 时间: Fri Jul 7 12:24:05 2006
: 给一个R*C的棋盘 (R,C <= 5000)，上面有B个黑格，其他皆为白格，(B <= 5000)
: 求一条切割线把棋盘分成两半，所有黑格皆在其中一边，
: 这条切割线只能往上或往右走，并且只能转弯K次 (K <= 1000)
: 请找出一个策略，让没有黑格的那一半棋盘面积最大。
: ┌─┬─┬─┬─┬─┬─┬─┐
: │ │ │ │ │ │ │ │
: ├─┼─┼─┼─╔═╪═╪═╡
: │ │ │ │ ║█│ │ │
: ├─┼─┼─┼─╫─┼─┼─┤
: │ │ │ │ ║ │ │ │
: ├─┼─╔═╪═╝─┼─┼─┤
: │ │ ║█│ │ │ │ │
: ├─┼─╫─┼─┼─┼─┼─┤
: │ │ ║ │ │█│ │ │
: ├─┼─╫─┼─┼─┼─┼─┤
: │ │ ║ │█│ │ │ │
: └─┴─╨─┴─┴─┴─┴─┘
不考虑转弯次数限制的话, greedy method 就可以找到 optimum solution
接下来做 dptable [5000个转角][1000次转弯]
dptable 里面存多出的白格数
Time complexity O(5000+5000*1000)
--
※ 发信站: 批踢踢兔(ptt2.cc)
◆ From: 140.109.21.102
1F：→ a127a127:可是更新一格dptable不是常数时间吧?推 07/07 14:21
2F：→ hil:O(5000+5000*1000) = O(1) :)推 07/07 14:27