題目:http://poj.org/problem?id=1160

題意:?一些村莊被建立在一條筆直的高速公路邊上,我們用一條坐標軸來描述這條高速公路，每一個村莊的坐標都是整數，沒

有兩個村莊坐標相同。兩個村莊間的距離，定義為它們的坐標值差的絕對值。我們需要在一些村莊建立郵局——當然，并不是每

一個村莊都必須建立郵局，郵局必須被建立在村莊里，因此它的坐標和它所在的村莊坐標相同。每個村莊使用離它最近的那個

郵局，建立這些郵局的原則是：所有村莊到各自所使用的郵局的距離總和最小。
? ??

你的任務是編寫一個程序，在給定了每個村莊坐標和將要建立的郵局數之后，按照上述原則，合理地選擇這些郵局的位置。

求出的所有村莊到距離它最近的郵局的距離總和.

分析:給定一個序列,假設我們要建一個郵局,那么一定是在這個序列的中點,所以我們可以先預處理出序列區間[l,r]之間建立

一個郵局的最短距離和w[l][r],然后用dp[i][j]表示到i個村莊建立j個郵局的最短距離和,那么就有狀態轉移方程:

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int INF = ~0U>>1; const int N = 305;int w[N][N]; int dp[N][35]; int a[N]; int n,m;void Init(int a[],int n) {memset(w,0,sizeof(w));for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)w[i][j] = w[i][j-1] + a[j] - a[(i+j)>>1]; }int Work() {for(int i=1;i<=n;i++){dp[i][i] = 0;dp[i][1] = w[1][i];}for(int j=2;j<=m;j++){for(int i=j+1;i<=n;i++){dp[i][j] = INF;for(int k=j-1;k<i;k++)dp[i][j] = min(dp[i][j],dp[k][j-1] + w[k+1][i]);}}return dp[n][m]; }int main() {while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++)scanf("%d",&a[i]);Init(a,n);printf("%d\n",Work());}return 0; }

總結

以上是生活随笔為你收集整理的邮局--dp经典问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。