百练162:Post Office

题目传送门

题目大意：

　　有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的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。