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