給定V個(gè)村莊的位置xi，建P個(gè)郵局，使每個(gè)村莊到最近的郵局的距離之和最小。P?<=?300,?P?<=?V?<=?3000,?1?<=?xi?<=?10000

這是個(gè)類2D1D的dp，狀態(tài)??由??轉(zhuǎn)移得到，依次推出以下結(jié)論：

時(shí),?并且

從而得到

從而有決策單調(diào)性

最后，當(dāng)我們需要求出的時(shí)候，只需要枚舉作為決策區(qū)間即可。注意到需要的值，所以需要倒著枚舉。

const int N = 3010, M = 310, inf = 1e9; int a[N], w[N][N], dp[N][M], m[N][M]; int v, p;void init_w() {for (int i = 1; i <= v; i ++){w[i][i] = 0;for (int j = i + 1; j <= v; j ++)w[i][j] = w[i][j - 1] + a[j] - a[(i + j) >> 1];}return; }int main() {int T = 1;//T = read();while (T --){v = read(); p = read();for (int i = 1; i <= v; i ++)a[i] = read();sort (a + 1, a + 1 + v);init_w();for (int i = 1; i <= v; i ++)dp[i][1] = w[1][i];for (int j = 2; j <= p; j ++){m[v + 1][j] = v;for (int i = v; i >= j; i --){int mn = inf, p;for (int k = max(m[i][j - 1], j - 1); k <= min(m[i + 1][j], i - 1); k ++)if (dp[k][j - 1] + w[k + 1][i] < mn){mn = dp[k][j - 1] + w[k + 1][i];p = k;}m[i][j] = p;dp[i][j] = mn;}}cout << dp[v][p];}return 0; }

總結(jié)

以上是生活随笔為你收集整理的luogu p4767 邮局的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。