※ 引述《pangfeng.bbs@ptt2.cc (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)