http://acm.pku.edu.cn/JudgeOnline/problem?id=1160

DP题

在一条笔直的公路上有一排城镇，要在城镇上建邮局，首先输入城镇数和要建的邮局数，问：所有城镇距离最近邮局的距离总和是多少？

题目思路：用w[i][j]记录把前i个邮局建到前j个村庄中的最优解，用distance[i][j]记录所有在i到j村庄中，建1个邮局的最小代价。显然邮局应该设到中点。让前i个邮局覆盖前j个村庄，第i+1个邮局覆盖第j+1至j+k个村庄(j+k<=n)，则状态转移方程为
w[i+1][j+k]=min{w[i][j]+distance[j+1][j+k];} (k+j<=n)。distance数组存放从i到j中有一个邮局的最小代价，显然该邮局应该放在中间。Opt[i][j] 表示前i个邮局覆盖前j个村庄的最小代价，对于i=1来说，w[i][j] = distance[i][j],让前2个邮局覆盖前j个村庄，也就是i=2的情况，可能是一下情况的最优解：第一个邮局覆盖第一个村庄，第二个村庄覆盖2-j个村庄，或者第一个邮局覆盖第1-2个村庄，第二个村庄覆盖3-j个村庄，第一个邮局覆盖第1-3个村庄，第二个村庄覆盖4-j个村庄

#include<stdio.h>
#include<string.h>
int distance[310][310];
int w[310][310];
#define max 3000000
int main()
{
    int i,j,k,m,n,middle,q,v[310];
 while(scanf("%d%d",&m,&n)!=EOF)
 {
  for(i=1;i<=m;i++)
   scanf("%d",&v[i]);
  memset(distance,0,sizeof(distance));
  for(i=1;i<=m;i++)
   for(j=i;j<=m;j++)                     
   {
    middle=(i+j)/2;
    for(k=i;k<=middle;k++)
     distance[i][j]=distance[i][j]+v[middle]-v[k];
    for(k=middle+1;k<=j;k++)
     distance[i][j]=distance[i][j]+v[k]-v[middle];
   }
  for(i=0;i<=n;i++)
   for(j=0;j<=m;j++)
    w[i][j]=max;
  w[0][0]=0;
  for(i=0;i<=n;i++)
   for(j=0;j<=m;j++)
    if(w[i][j]<max)
    {
     for(k=1;k<=m-j;k++)
     {
      q=w[i][j]+distance[j+1][j+k];
      if(w[i+1][j+k]>q)
       w[i+1][j+k]=q;
     }
    }
  printf("%d\n", w[n][m]);
 }
 return 0;
}