題目傳送門

題目大意：

　　有v個村莊，每個村莊有各自的位置，且每個位置互不相同。現在要在村莊上設立P個郵局，使每個村莊到最近的郵局的距離之和最小。

分析：

方法一：

　　這是一個動態規劃的問題，dp狀態比較容易想到，定義狀態d[i][k]表示前i個村莊，在這i個村莊中設立k個郵局時，所有村莊到這k個郵局的最小距離

　　狀態轉移方程 dp[i][j] = min( dp[k][j-1] ?- ?在dp[k][j-1]的狀態下再設第j個郵局時少花費的距離）

　　 k = j-1...min(i,p) 注意一定是min(i,p)否則就把設立大于p個郵局的情況加進去了，樣例過了，但是會WA

代碼：

#include <cstdio> #include <cstring> int a[302]; int dp[302][32]; int abs(int x){return x > 0 ? x : -x;} int min(int a,int b){return (a < b)? a : b;} int post[302]; //post[i] = Σ(a[j] - a[i]) j=i+1...n int main(){int n,m;scanf("%d%d",&n,&m);memset(dp,0x3f3f3f,sizeof(dp));for(int i = 1;i <= n;i++)scanf("%d",&a[i]);for(int i = 1;i <= n;i++){int temp = 0;for(int j = 1;j <= n;j++){if(j != i)temp += abs(a[j] - a[i]);if(j > i)post[i] += a[j] - a[i];}dp[i][1] = temp;}for(int i = 2;i <= n;i++){for(int k = 2;k <= i && k <= m;k++){int minT = 0x3f3f3f; //計算在dp[k][j-1]的狀態下再設第j個郵局時少花費的距離for(int j=k-1;j < i;j++){int now = 0,pre = 0;now = post[i];pre = post[j];for(int p = j+1;p < i;p++){if(a[p] + a[p] > a[i] + a[j])now += a[i] - a[p];else now += a[p] - a[j];}if(dp[j][k-1] + now - pre < minT){minT = dp[j][k-1] + now - pre;}}dp[i][k] = minT;}}int ans = 0x3f3f3f;for(int i = m;i <= n;i++)ans = min(ans,dp[i][m]);printf("%d",ans);} View Code

?

方法二：方法一的狀態轉移方程每次的計算量比較大，而且計算起來稍微有些麻煩，在機試中時間是很寶貴的，看了一篇博客的關于這道題的講解，比方法一簡單許多 ? 博客傳送門

首先它的狀態含義和方法一的不一樣，方法一中 dp[i][j] 考慮的是全部村莊到現在的狀態花費的距離之和，其實后面的距離每次算的方法都是一樣的，不如提出來不放在狀態中，于是：

定義狀態d[i][j]表示前i個村莊，在這i個村莊中設立j個郵局的最小距離。（注意：不考慮村莊i之后的村莊）

s[i][j]表示村莊i至村莊j這幾個村莊中設立一個郵局的最小距離。如果設立一個郵局，那么郵局設立在(a+b)/2這個位置是最優的。所以可以分解成以下子問題：

d[i][j]的最小值為d[k][j-1]的最小值加上s[k+1][i]，s[k+1][i]為在k+1至i這幾個村莊中設立一個郵局的最小距離。

?????? d[i][j]=min(d[i][j], d[k][j-1]+s[k+1][i])

?????? 邊界條件d[i][1]=s[1][i].

?????? s數組可做如下優化：

?????? s[1][4]，把郵局設立在2和設立在3上距離是相同的。x2-x1+x3-x2+x4-x2與x3-x1+x3-x2+x4-x3相等。s[1][5]是把郵局設立在3上，s[1][5]=s[1][4]+x[5]-x[3]。

由此，可得出遞推式：s[i][j]=s[i][j-1]+x[j]-x[(i+j)/2].

#include <iostream> #include <cstdio> using namespace std;const int INF=1e8; int x[305]; int d[305][35]; int s[305][305];int main() {//freopen("in.txt","r",stdin);int n,p;while(~scanf("%d%d",&n,&p)){for(int i=1;i<=n;i++)scanf("%d",&x[i]);for(int i=1;i<=n;i++)for(int j=1;j<i && j<=p;j++)d[i][j]=INF;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++)s[i][j]=s[i][j-1]+x[j]-x[(i+j)/2];d[i][1]=s[1][i];}for(int i=2;i<=n;i++)for(int j=2;j<=i && j<=p;j++)for(int k=j-1;k<i;k++)d[i][j]=min(d[i][j],d[k][j-1]+s[k+1][i]);printf("%d\n",d[n][p]);}return 0; } View Code

總結

　　在思考問題，寫狀態方程時要力求簡潔，公式化，當狀態方程比較繁瑣的時候，會增加寫代碼的難度——也就意味著花費更多的時間（寫和調試的時間）。并且最開始我寫方法一的代碼超時了，經過修改后才AC的。

轉載于:https://www.cnblogs.com/starryxsky/p/7136050.html

總結

以上是生活随笔為你收集整理的百练162:Post Office的全部內容，希望文章能夠幫你解決所遇到的問題。

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