[정수리] 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과 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 <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#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<<dp[P][V]<<endl;
	return 0;
}