Re: [請益] 好題目q:

※ 引述《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
→ a127a127:可是更新一格dptable不是常數時間吧?
→ hil:O(5000+5000*1000) = O(1) :)