看板ACMCLUB
標 題[請益] 好題目q:
發信站批踢踢兔 (Fri Jul 7 12:25:18 2006)
轉信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt2
※ [本文轉錄自 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