看板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