※ 引述《[email protected] (P老师)》之铭言： : 有一题阶梯状棋盘放最少数目的车, 那题有人记得做法吗? : 阶梯状棋盘是说每一排的起点及终点都不能在上一排的左边. 像这样: : XXX : XXXX : XXXXX : XXXXXXX : XXX : 题目问如何放最少数目的车, 让每一格都会被至少一只车攻击 (像八后那样). 嗯...我有一个很greedy的解法... 可是不确定对不对...麻烦大家看一下~谢谢~~~ 以下面这个为例子... XXX 从最上面那一列开始考虑 XXX 如果选择在那一列放车(只考虑那一列) XXXXX 那麽会有 3:1 (平均每车占三格) XXXX 如果选择不在那一列放车 XXXX 那麽那一列所占的那几行(共三直行)都必须有车 X 此时(只考虑直行) 会有 3+3+5:3(三个直行) X 因为 11/3 > 3/1 所以我希望最左边三个直行都要有车... (做个记号) 以此类推，对每横列做相同的考虑，得到: vvv v XXX XXX > XXXXX > XXXX > XXXX X X 接下来用greedy的方式由左->右 且上->下的方式放车... vvv v XXX XOX //如果该横列已经有车,那麽将车往下/上移动一格(下优先) > OXXXX > OXXX > XXXO X X 因此4车是最少的放法... 由於每次只考虑横列 所以也要把每次考虑直行算进去... 但是此时发现结果不太一样...要取最小值 所以我觉得我的想法怪怪的...麻烦大家帮忙想一下证明or反例...谢谢~~~ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.57.152.57 ※ 编辑: pigalan 来自: 61.57.152.57 (05/19 00:19)