※ [本文轉錄自 hil 看板]
作者: pp5438 (厄阿) 看板: hil
標題: [請益] 好題目q:
時間: Fri Jul 7 12:24:05 2006
給一個R*C的棋盤 (R,C <= 5000)，上面有B個黑格，其他皆為白格，(B <= 5000)
求一條切割線把棋盤分成兩半，所有黑格皆在其中一邊，
這條切割線只能往上或往右走，並且只能轉彎K次 (K <= 1000)
請找出一個策略，讓沒有黑格的那一半棋盤面積最大。
┌─┬─┬─┬─┬─┬─┬─┐
│ │ │ │ │ │ │ │
├─┼─┼─┼─╔═╪═╪═╡
│ │ │ │ ║█│ │ │
├─┼─┼─┼─╫─┼─┼─┤
│ │ │ │ ║ │ │ │
├─┼─╔═╪═╝─┼─┼─┤
│ │ ║█│ │ │ │ │
├─┼─╫─┼─┼─┼─┼─┤
│ │ ║ │ │█│ │ │
├─┼─╫─┼─┼─┼─┼─┤
│ │ ║ │█│ │ │ │
└─┴─╨─┴─┴─┴─┴─┘
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.122.107.57
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 140.122.107.57