POJ 1160：Post Office 郵局經典DP

 

Post Office Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 17168   Accepted: 9270

 

Description

There is a straight highway with villages alongside the highway. The highway is represented as an integer axis, and the position of each village is identified with a single integer coordinate. There are no two villages in the same position. The distance between two positions is the absolute value of the difference of their integer coordinates.

Post offices will be built in some, but not necessarily all of the villages. A village and the post office in it have the same position. For building the post offices, their positions should be chosen so that the total sum of all distances between each village and its nearest post office is minimum.

You are to write a program which, given the positions of the villages and the number of post offices, computes the least possible sum of all distances between each village and its nearest post office.

Input

Your program is to read from standard input. The first line contains two integers: the first is the number of villages V, 1 <= V <= 300, and the second is the number of post offices P, 1 <= P <= 30, P <= V. The second line contains V integers in increasing order. These V integers are the positions of the villages. For each position X it holds that 1 <= X <= 10000.

Output

The first line contains one integer S, which is the sum of all distances between each village and its nearest post office.

Sample Input

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

Sample Output

9

題意是給了V個村莊，要在這些村莊中選出P個建立郵局，要求的是建成了P個郵局之後，所有村莊到郵局的距離最短。求最短距離。

沖著郵局的經典DP做的。暴力的話肯定TLE，所以只能往DP上想。

然後就從小了開始想，如果是從a點到b點(中間b-a+1個村莊)建立1個郵局的話，那肯定是要建在中間的村莊上沒跑了。1和3的話，要建在2。1和4的話建在2或者3都行因為距離是一樣的。

然後這個規律自己做得時候也發現了:

用sum[i][j]表示村莊i到村莊j建立一個郵局的距離。那麼推導有sum[i][j]=sum[i][j-1]+value[j]-value[(i+j)/2]

你看，sum[1][4](建在2或者3)=(value[4]-value[3])+(value[3]-value[2])+(value[3]-value[1])

=value[4]+value[3]-value[2]-value[1]

而sum[1][5](建在3)=(value[5]-value[3])+(value[4]-value[3])+(value[3]-value[2])+(value[3]-value[1])

=value[5]+value[4]-value[2]-value[1]

通過這樣可以發現這個規律：sum[i][j]=sum[i][j-1]+value[j]-value[(i+j)/2]

 

所以這樣就把建在1到V個村莊的P個郵局這個問題拆開了，知道了某部分建立一個郵局的最優解，之後就是dp推導。

用dp[i][j]表示從1到j個村莊建立第i個郵局時的最優解，則有dp[i][j]=min(dp[i][j],dp[i-1][k-1]+sum[k][j]);

上面的推導公式表示將1到j個村莊建立i個郵局分成兩部分，一部分是1到k-1個村莊建立i-1個郵局的最優解，另一部分是k到j建立一個郵局的最優解，不斷從1到j枚舉k的取值，選出最小的值即是最優解。

做這道題有一個問題當時想不出來是起始值不知道怎麼確定，現在總結的話，真是豬頭啊光速小子。初始值不就是dp[1][i]=sum[1][i]啊。當時居然完全沒思路想不出來。。。

代碼：

 

#include 
#include 
#include 
#include 
#include 
#include 
#pragma warning(disable:4996)
using namespace std;

int V,P;
int value[305];

int sum[305][305];
int dp[35][305];

int main()
{
	int i,j,k;
	memset(sum,0,sizeof(sum));
	for(i=0;i<=30;i++)
	{
		for(j=0;i<=300;j++)
		{
			dp[i][j]=10000;
		}
	}
	cin>>V>>P;

	value[0]=0;
	for(i=1;i<=V;i++)
	{
		cin>>value[i];
	}
	sum[1][2]=value[2]-value[1];
	for(i=1;i<=V;i++)
	{
		for(j=i+1;j<=V;j++)
		{
			sum[i][j]=sum[i][j-1]+value[j]-value[(i+j)/2];
		}
	}

	for(i=1;i<=V;i++)//！！！！起始值
	{
		dp[1][i]=sum[1][i];
	}

	for(i=2;i<=P;i++)
	{
		for(j=i;j<=V;j++)
		{
			for(k=1;k<=j;k++)
			{   
				dp[i][j]=min(dp[i][j],dp[i-1][k-1]+sum[k][j]);
			}
		}
	}
	cout<