推 walkwall:所以中間是用風車狀區塊(3x3四個包圍1x1一個)當主體嗎 06/01 16:45
可以這樣子 但是 邊緣不好處理
※ 編輯: EIORU 來自: 220.130.210.241 (06/03 12:04)
如果你問的是給定任意 N 值，求最高分，那麼每個 N 都算是一個獨立問題。
如果你問的是所有 N 中分數密度的最大值，那麼最大值是沒有的，只有上限；
並且那個上限值就是中間區域 walkwall 說的風車排法，也就是
4 * 100 / (4 * 9 + 1) = 400 / 37
因為對任何 N，你一定可以用風車把 (N-14)^2 以上的格數蓋滿，
剩下的用沒分數的 1x1 填滿也無所謂。這樣你會確定得到
(400 / 37) * (N-14)^2 / N^2
以上的分數。這個保證得分隨著 N 變大會趨近 400 / 37，
而這個值已經是「不限定區域要是正方形」的前提下的最大值，
所以沒有任何「限定排成正方形」的排法可以超越它。
所以如果我沒有誤解你的意思，這種題目不需要考慮邊緣，
walkwall 推文那一行就解完了。 :3
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.202.140
→ killyou:密度應該是100/(3x3+1) 形狀像用"ㄈb"分割整個平面 06/04 12:28
推 pikacha:附議樓上,出題的作者可是要求有邊緣的!!! 06/04 12:32
→ isnoneval:四個 3x3 用一個 1x1 就夠了 1:1 分數密度較低 06/04 12:44
→ isnoneval:pikacha 你有仔細看我講的嗎 XD 06/04 12:44
推 grooving:同意 用風車排法當邊長越大單位分數會越趨近一個值 06/04 12:49
→ grooving:剩下的 就是証明這個值都大於其他排法 06/04 12:52