POJ 1160 Post Office(dp)

제목 설명: Post Office Time Limit: 1000MS Memory Limit: 10000K
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개 우체국은 어느 p개 마을에 세워져 있는지 물어보면 각 마을이 가장 가까운 우체국까지의 거리와 가장 작다.
제목 분석: 우선 이 문제를 풀고 난 후에 이 문제가 괜찮은 것 같다. 배열 조합에 대한 학습의 의미가 매우 크다. 나는 이 문제를 처음 봤을 때 생각이 없다. 욕심을 부리고 내가 생각하는 욕심을 부리는 방법에 따라 한다. 확실한 사례는 있지만 코드가 실현되기에는 너무 힘들다. 그래서 dp가 아닐까 생각한다.그래서 정의: dp[i][j]: 전 i개 도시에서 j개 우체국과 최소치를 놓았는데 이렇게 정의한 후에 어떻게 점차적인 관계를 찾아낼 수 있습니까?사실 저는 다른 사람이 쓴 블로그를 참고했습니다. 이 블로그에 대해 저는 101점을 주었습니다. 왜냐하면 이 블로거는 저와 같이 상세한 사고방식을 썼기 때문입니다. (그리고 도해) 코드를 아무렇게나 묻히거나 간단하게 두 마디만 하면 끝나는 것이 아니라 다른 사람의 블로그 주소를 첨부하려고 했는데 이것은 예전에 만든 제목이어서 찾을 수 없습니다.블로거가 날 보면 말해도 돼.그러나 블로거의 사고방식은 내가 기억하는 전 i개 도시에 j개의 우체국을 두었다. 우리는 1개의 우체국을 뜯어내고 이 i개 도시를 두 부분으로 나눈다. 0~k는 j-1개의 우체국, k+1~i는 1개를 놓았다. 그러면 우리는 k를 0~i-1에서 순환하고 최대치를 얻으면 모든 상황을 요약할 수 있다. 0~k에서 j-1개의 우체국을 놓았다. 분명히 우리 dp수조가 저장한 물건은 직접 호출할 수 있다.그러면 우리가 a~b에서 우체국의 거리와 미리 열거를 해야 한다. 이 열거 방법은 바로 여기에 도시를 추가하고 이전에 얻은 값으로 업데이트하면 된다. (코드를 보면 알 수 있다) 코드:

#include "stdio.h"
#include "algorithm"
using namespace std;
#define INF 1e8
int pos[300+5];
int dp[300+5][30+5];
int d[300+5][300+5];
int main()
{
    int v,p,i,j,k;
    while(scanf("%d%d",&v,&p)!=EOF)
    {
        for (i = 1; i <= v; i += 1)
        {
            scanf("%d",&pos[i]);
        }
        for(i=1;i<v;i++)
        {
            for(j=i+1;j<=v;j++)
            {
                //              ，       ，       
                d[i][j]=d[i][j-1]+pos[j]-pos[(i+j)/2];
            }
        }
        for(i=1;i<=v;i++)
        {
            for(j=0;j<=p&&j<=i;j++)
            {
                if(j==0){
                    //0                
                    dp[i][0]=INF;continue;
                }
                if(i==j){
                    dp[i][j]=0;continue;
                }
                //       dp      ，                   INF
                dp[i][j]=INF;
                for(k=j-1;k<i;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[k][j-1]+d[k+1][i]);
                }
            }
        }
        printf("%d
",dp[v][p]);
    }
    return 0;
}