【题目描述】
有一条笔直的高速公路，路旁分布着一些村庄。公路可以用一条数轴表示，则村庄的位置就是其坐标。没有两个村庄的坐标相同。两个村庄之间的距离就是它们坐标之差的绝对值。 一些——但不一定是所有的村庄将修建邮局。邮局和该邮局所在的村庄处于同一位置。应当仔细选择邮局的位置，使得所有村庄到最近邮局的距离总和最短。 你要编写一个程序，给出所有村庄的坐标和计划修建的邮局个数，计算所有村庄到最近邮局的距离总和的最小可能值。
【输入格式】
输入文件的第一行有2个正整数：村庄数V(1<=V<=300)，邮局数P(1<=P<=30)，P<=V。 第二行有V个正整数，分别代表N个村庄的坐标。坐标的范围是[1,10000]，坐标按递增顺序给出。
【输出格式】
输出一行一个正整数S，即所有村庄到最近邮局的距离总和的最小可能值。
【样例输入】
10 5 1 2 3 6 7 9 11 22 44 50
【样例输出】
9
【提示】
对于30%的数据，1<=P<=N<=10. 对于100%的数据，1<=P<=30,1<=N<=300,P<=N.
【题解】
本题不太好想，我们可以本着特殊到一般的思想，先考虑村庄i到村庄j之间只有一个邮局的情况。那么这个邮局就一定在i和j的中点处。 令dis[i][j]表示i到j之间只有一个邮局时的距离和，则 dis[i][j]=dis[i][j-1]+pos[j]-poj[(i+j)>>1]; 下面我们来考虑多个邮局的情况，同样可有递推式：令dp[i][j]表示前i个村庄建了j个邮局的距离最小和，则 dp[i][j]=dp[k][j-1]+dis[k+1][i]; (j-1 <= k < i) 有点类似C(N,M)=C(N-1,M)+C(N-1,m-1)吧？ 其实就是前k个村庄修了j-1个邮局，后面再修一个的最小值。 边界情况： dp[i][i]=0//每村一个 dp[i][1]=dis[1][i]//只有一个
代码如下：
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> #include<math.h> #define ll long long #define inf 0x7f7f7f7f #define N 305 #define M 35 using namespace std; int n,m,x[N],dis[N][N],dp[N][M]; int main() { freopen("postoffice.in","r",stdin); freopen("postoffice.out","w",stdout); while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=n;i++) scanf("%d",&x[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) dis[i][j]=dis[i][j-1]+x[j]-x[(i+j)/2]; for(int i=1;i<=n;i++) { dp[i][i]=0; dp[i][1]=dis[1][i]; } for(int j=2;j<=m;j++) for(int i=j+1;i<=n;i++) { dp[i][j]=inf; 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[n][m]); } return 0; }P.S.感觉POJ有毒，COGS上1Y，POJ上一直都是RE……
