DP。

dp[i][j] 表示 用 i 個郵局 覆蓋 j 個點。

dp[i][j] = min(dp[i-1][k]+W[k+1][j])

W[i][j] 表示 第i點 到 第j點 建1個郵局 所需的cost,顯然為 Sigma(k=i~j){ |X[k] - X[mid(i, j)]| }。

所以就先 O(n^3) 建 cost表,然後再 O(n^3) DP。

另外這題也符合 四邊形不等式,所以可以降到 O(n^2),不過 O(n^3) 就夠了。

我的code

http://codepad.org/wMdttioa

p.s: 關於 四邊形不等式 可以參考這篇 http://blog.csdn.net/find_my_dream/article/details/4931222

       我覺得他寫的證明還不錯,比 momo 好懂XD。

 

 

文章標籤
創作者介紹

jghs1328

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