题目含义
v个村庄要建p个邮局
现给出每个村庄的位置，并且邮局只能建在村庄的位置
问每个村庄到离它最近的邮局距离之和最小为多少
题目分析
区间dp[i][j]表示在前i个村庄建j个邮局的最小距离
dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][j])
这个状态方程表示，将【在前i个村庄建j个邮局的距离】划分成【在前k个村庄建j-1个邮局的距离】加上【在第k+1个村庄到第j个村庄之间建一个邮局的距离】
题目代码
#include<iostream> #include<stdio.h> #include<string.h> #include<queue> using namespace std; typedef long long LL; const int INF=0x3f3f3f3f; int v,p; int a[307],dis[307][307],dp[307][307]; int main(){ scanf("%d%d",&v,&p); for(int i=1;i<=v;i++){ scanf("%d",&a[i]); } memset(dis,0,sizeof(dis)); for(int i=1;i<=v;i++) for(int j=i+1;j<=v;j++){ dis[i][j]=dis[i][j-1]+a[j]-a[(i+j)/2]; } memset(dp,INF,sizeof(dp)); for(int i=1;i<=v;i++){ dp[i][i]=0; dp[i][1]=dis[1][i]; } for(int j=2;j<=p;j++) for(int i=j+1;i<=v;i++){ for(int k=j-1;k<i;k++) dp[i][j]=min(dp[i][j],dp[k][j-1]+dis[k+1][i]); } printf("%d\n",dp[v][p]); return 0; }
原文：https://www.cnblogs.com/helman/p/11246720.html