難得的中文題目XD。

把算式畫簡一下得 => Sigma ((xi)^2) /n - average^2

因為 n, average 都是定值,所以只要 DP 找出 Sigma 最小就好了。

O(n^6)建出 SUM[x1][x2][y1][y2] = ([(x1, y1), (x2, y2)] 這塊矩形的總和) ^ 2。

DP[k][x1][x2][y1][y2] = [(x1, y1), (x2, y2)] 這塊矩形分割成 k 塊 的最小平方和。

=> 轉移式

DP[k][x1][x2][y1][y2]

= min (DP[k-1][x1][f][y1][y2]+SUM[f+1][x2][y1][y2], DP[k-1][f+1][x2][y1][y2]+SUM[x1][f][y1][y2], DP[k][x1][x2][y1][y2])

DP[k][x1][x2][y1][y2]

= min (DP[k-1][x1][x2][y1][f]+SUM[x1][x2][f+1][y2], DP[k-1][x1][x2][f+1][y2]+SUM[x1][x2][y1][f], DP[k][x1][x2][y1][y2])

 

我的code

http://codepad.org/xMggVX1T

p.s: 變數不要打錯了XD。

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()