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

先講講我的思路：這道題首先很容易想到是用動態(tài)規(guī)劃思想，所以我定義了一個二維數(shù)組dp[i][j]，表示前j個位置，修建了i個郵局。所以推導出的狀態(tài)轉(zhuǎn)移方程為：

dp[i][j] = min{dp[i][j-1]+第j個位置到第i個郵箱位置的差，dp[i-1][k] + 第j個位置到第k+1個位置的差}，實際上花括號里，左邊代表第i個郵箱不在第j個位置上，而右邊代表第i個

郵箱在第j個位置上，為了能夠確定dp[i][j]中第i個郵箱建立的位置，我用一個chosen[i][j]記錄下來，表示前j個位置中，第i個郵箱建立的位置，這樣就可以直接計算第j個位置與

第i個郵箱位置的差。。此外，如果第i個郵箱有多個位置都滿足要求的話，那么盡可能地往右邊建。。

但是一直是WA。。。沒有想通到底是哪里出了問題。。。

WA:

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;const int maxn = 3300; const int inf = 0x3fff; int n,m,pos[maxn],dp[33][maxn],chosen[33][maxn];int main() { while(scanf("%d%d",&n,&m)!=EOF){memset(dp[0],0,sizeof(dp[0]));memset(chosen,0,sizeof(chosen));for(int i = 1; i <= n; i++)scanf("%d",&pos[i]);for(int j = 1; j <= n; j++)for(int k = j-1; k >= 1; k--)dp[0][j] += pos[j]-pos[k];for(int i = 1; i <= m; i++)for(int j = 1; j<= n; j++)dp[i][j] = inf;for(int i = 1; i <= m; i++) {dp[i][i] = 0;chosen[i][i] = i;}for(int j = 2; j <= n; j++){int sum = 0, choose = 0;dp[1][j] = dp[0][j];for(int k = j-1; k >= 1; k--){sum = 0;for(int t = k+1; t <= j; t++) sum += pos[t] - pos[k];if((dp[0][k]+sum < dp[1][j]) || ((dp[0][k]+sum == dp[1][j]) && (choose == 0))){dp[1][j] = dp[0][k] + sum;chosen[1][j] = k;choose = 1;}}}for(int i = 2; i <= m; i++)for(int j = i+1; j <= n; j++){if(dp[i][j-1] != inf){dp[i][j] = dp[i][j-1] + pos[j] - pos[chosen[i][j-1]];chosen[i][j] = chosen[i][j-1];}int sum = 0,choose = 0;for(int k = j-1; k >= i; k--){if(dp[i-1][k] != inf){if((dp[i-1][k] + sum < dp[i][j]) || ((dp[i-1][k] + sum == dp[i][j]) && (choose == 0))){dp[i][j] = dp[i-1][k] + sum;chosen[i][j] = j;choose = 1;}}sum += pos[j] - pos[k];}}printf("%d\n",dp[m][n]);}return 0; }

別人的思路：

1、考慮在V個村莊中只建立一個郵局的情況，顯然可以知道，將郵局建立在中間的那個村莊即可。也就是在a到b間建立

一個郵局，若使消耗最小，則應該將郵局建立在（a+b)/2這個村莊上。

2、下面考慮建立多個郵局的問題，可以這樣將該問題拆分為若干子問題，在前i個村莊中建立j個郵局的最短距離，是

在前k個村莊中建立j-1個郵局的最短距離與 在k+1到第i個郵局建立一個郵局的最短距離的和。而建立一個郵局我們在

上面已經(jīng)求出。

3、狀態(tài)表示，由上面的討論，可以開兩個數(shù)組

dp[i][j]:在前i個村莊中建立j個郵局的最小耗費

sum[i][j]:在第i個村莊到第j個村莊中建立1個郵局的最小耗費

那么就有轉(zhuǎn)移方程：dp[i][j] = min(dp[i][j],dp[k][j-1]+sum[k+1][i])? DP的邊界狀態(tài)即為dp[i][1] = sum[1][i];

所要求的結果即為dp[V][P];

4、然后就說說求sum數(shù)組的優(yōu)化問題，可以假定有6個村莊，村莊的坐標已知分別為p1,p2,p3,p4,p5,p6;那么，如果要

求sum[1][4]的話郵局需要建立在2或者3處,放在2處的消耗為p4-p2+p3-p2+p2-p1=p4-p2+p3-p1放在3處的結果為p4-

p3+p3-p2+p3-p1=p4+p3-p2-p1，可見，將郵局建在2處或3處是一樣的。現(xiàn)在接著求sum[1][5],現(xiàn)在處于中點的村莊是

3，那么1-4到3的距離和剛才已經(jīng)求出了，即為sum[1][4],所以只需再加上5到3的距離即可。同樣，求sum[1][6]的時候

也可以用sum[1][5]加上6到中點的距離。所以有遞推關系：sum[i][j] = sum[i][j-1] + p[j] -p[(i+j)/2]

公式，還是公式的推理....

總結

以上是生活随笔為你收集整理的poj 1160(Post Office)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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