→ march20:咦? 沒有人要幫我 prove 或 disprove 嗎 XD 11/15 15:34
先來大膽假設一件事:
在所有最佳解中, 至少有一個是符合這個 pattern
┌───┬───┐
│ │ │
│ A │ B │
│ │ │
├───┴───┤
│ │
│ C │
│ │
└───────┘
其中 A 為正方型, B 和 C 為矩型 (可能為正方型, 也可能為長或寬為 0 的退化矩型)
如果是這樣, 就可以用 DP 解了:
令原題矩型 width 為 w, height 為 h
求出所有 m x n 矩型的最佳解 S(m, n) // where 0<=m<=w, 0<=n<=h, m<n
(m x n 跟 n x m 意義相同, 限定 m < n || n < m 可以省掉一半的 case)
然後找出最小的 A,B,C 組合, 使得 S(mB, nB) + S(mC, nC) 最小.
不過得先證明以上假設正確 (逃)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 128.54.43.37
※ 編輯: march20 來自: 128.54.43.37 (11/14 05:36)
※ 編輯: march20 來自: 128.54.43.37 (11/14 05:38)
※ 編輯: march20 來自: 128.54.43.37 (11/14 05:39)