推 willieliao:thanks a lot for your thought. 11/13 08:59
→ grence:喔喔，想簡單了..囧> 11/13 17:20
推 march20:感覺得用 DP 才能處理 @@ 11/14 05:14
※ 引述《yoco315 (眠月)》之銘言：
: 想是這樣想..
: 問題是有辦法證明嗎 @@?
: 我想了十分鐘 想不到 T____T
: 希望高手解答
前面有人推文說囉
簡單的說, greedy 是錯的
不過沒花時間下去找答案
這應該是有人做過研究的
舉例來說, 7x8 的區域
依照輾轉相除 (或相減, 都等價) 的概念
會用到 7x7 的 1 個
1x1 的 7 個
┌──────┬┐
│ ├┤
│ ├┤
│ ├┤
│ ├┤
│ ├┤
│ ├┤
└──────┴┘
實際上的最少應該是
4x4 的 2 個
3x3 的 2 個
2x2 的 1 個
1x1 的 2 個
┌───┬───┐
│ │ │
│ │ │
│ │ │
├─┬─┴┬──┤
│ │ │ │
├┬┤ │ │
└┴┴──┴──┘
補充一下板友的意見給大家參考
--
有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。
存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你
，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也
是比較不容易被擊倒的人。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.56