作者march20 ()
看板Prob_Solve
标题Re: [问题] 长方形与正方形
时间Tue Nov 14 05:34:06 2006
先来大胆假设一件事:
在所有最佳解中, 至少有一个是符合这个 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)
1F：→ march20:咦? 没有人要帮我 prove 或 disprove 吗 XD 11/15 15:34