poj1160(Post Office)

      題目連結：http://poj.org/problem?id=1160

      題意：有N個村莊，要在這N個村莊中建K個郵局，求如何布置這些郵局能使得所有村莊到離它最近的那個郵局的距離總和最小。

代碼：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define INF 10000000
int v[305];
int V,P;
int dp[35][305],dis[305][305];
//dp[i][j]表示前i個郵局建在前j個村莊時的最小距離
//dis[i][j],表示有1個郵局在村莊i與j之間時，村莊i至村莊j到郵局的最短距離總和
void Ini()
{
	int i,j,k;
	int mid;
	memset(dis,0,sizeof(dis));
	for(i=1;i<=V;i++)
	{
		for(j = i+1;j<=V;j++)
		{
			mid= (i+j)/2;//一個郵局建在中間的那個村莊，能使得所有村莊到該郵局的距離總和最小
			for(k=i;k<=j;k++)
				dis[i][j] += abs(v[k]-v[mid]);
		}
	}
}
void DP()
{
	int i,j,k;
	for(i=2;i<=V;i++)
		dp[1][i] = dis[1][i];
	for(i=2;i<=P;i++)
		for(j=1;j<=V;j++)
		    dp[i][j] = INF;
	for(i=2;i<=P;i++)
		for(j=i;j<=V;j++)
			for(k=i;k<=j;k++)
			{
				if(dp[i][j] > dp[i-1][k] + dis[k+1][j])
					dp[i][j] = dp[i-1][k] + dis[k+1][j];
			}

}
int main()
{
	while(scanf("%d%d",&V,&P)!=EOF)
	{
		for(int i=1;i<=V;i++)
			scanf("%d",&v[i]);
		Ini();
		DP();
        printf("%d\n",dp[P][V]);
	}
	return 0;
}