poj 1160 Post Office（邮局问题）

Description

Input

Output

Sample Input

10 5
1 2 3 6 7 9 11 22 44 50

Sample Output

9

Source

就是邮局问题。

对于在1~n的村庄中建立m个邮局，要求所有村庄到邮局的距离最小。

多个邮局难解，可以先看一个邮局。在1~n中，建一个邮局，可以建在中间，一定是保证总距离最小的。如果建m个，那么就可以认为：在1~k村庄之间已经建了m-1个，然后在在k~n村庄之间只要建一个就够了。而建这一个邮局的最短距离是可以得到的。由此，我们可以将问题分解为多个子问题。

对于这样的一个问题，可以设一个dp[i][j]，表示在1~i的村庄中建立了j个邮局的最短总距离。

所以我们可以得到状态转移方程： dp[i][j]=max(dp[i][j],dp[k] [j-1]+sum[k+1] [ j ])

其中sum[i][j]是从i到j的村庄建立一个邮局的最小距离。可以得到：sum[ i ][ j ]=sum[i][j-1]+x[j]-x[ (i+j )/2 ] ;

那么就可以得到dp 的边界：dp[i][1]=sum[1][i];

#include<stdio.h>
#include<string.h>
int min(int a,int b)
{
	if(a<b)return a;
	else return b;
}
int main()
{
	int V,P,i,j,k,l,x[305],dp[305][305],sum[305][305];
	while(scanf("%d%d",&V,&P)!=EOF)
	{
		memset(sum,0,sizeof(sum));
		for(i=0;i<305;i++)
		for(j=0;j<305;j++)
		dp[i][j]=10000000;
		for(i=1;i<=V;i++)
		{
		scanf("%d",&x[i]);
		sum[i][i]=0;
		}
		for(i=1;i<=V;i++)
		for(j=i+1;j<=V;j++)
		{
		   	sum[i][j]=sum[i][j-1]+x[j]-x[(i+j)/2];
		}
		for(i=1;i<=V;i++)
		dp[i][1]=sum[1][i];
	
	for(j=1;j<=P;j++)
		{
		for(i=j+1;i<=V;i++)
			{
				for(k=1;k<=i;k++)
				dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k+1][i]);
			}
		}
		printf("%d\n",dp[V][P]);
	}
	return 0;
}

poj 1160 Post Office（邮局问题）

原文：http://blog.csdn.net/aaaaacmer/article/details/46929497