poj1160 Post Office 사각형 최적화 dp

Post Office
Time Limit: 1000MS
 
Memory Limit: 10000K
Total Submissions: 14051
 
Accepted: 7576
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

Source
IOI 2000
분석해 보면 이 문제는 아주 좋은 dp문제입니다. 먼저, dp[i][j]는 0에서 i까지 j개의postoffice를,sum[i][j]는 i에서 j까지 하나의postoffice를 배우는 최단길을 의미합니다!
그러면 dp[i][j]=dp[k][j-1]+sum[k+1][j](k>=0k<=i);
sum[i][j]=sum[i][j-1]+p[i]-p[(i+j)/2];
우리 이 두 가지 양식을 말해 보자!
우선, 우리는 짝수 개 점 중에서 우체국을 건설하는 가장 짧은 방법은 바로 중간에 있는 두 점, 그리고 이 두 점의 거리가 등가라는 결론을 얻을 수 있다.
예를 들어 p0,p1,p2,p3은 우리가 p1,p2를 어디에 세워도 하나이고 모두 p3-p1+p2-p0이다. 이 점은 모든 짝수 개점, 홀수 개점까지 확대할 수 있다. 자연히 가장 중간에 있다.
그런데 점이 하나밖에 없어요!만약에 저희가 점을 하나 더 넣고 싶다면요?위의 p0,p1,p2,p3에 p4를 추가하면 어떻게sum[i][j-1]에서sum[i][j]로 밀어냅니까?저희가 발견할 수 있어요.
p4에서 p2까지의 거리, 즉 p[j]-p[(i+j)/2]만 추가하면 돼요. 사실 이 예는 간단하지만 일반적인 상황으로 미루어도 돼요.
홀수 점은요?예를 들어 p0,p1,p2,p3,p4에 p5를 더하면 최단길은 어떻게 계산합니까?우리가 뻔히 알 수 있는 것도 p[j]-p[(i+j)/2]!
우리 첫 번째 식이 온다고 다시 말하자면,
우리는 0에서 i까지 j개의 우체국을 놓는 가장 짧은 방법은 틀림없이 0에서 i의 어느 지점 k에서 얻을 수 있다는 것을 알 수 있다. 즉, dp[k][j-1]에서 얻을 수 있다. 왜냐하면 우리는 k를 0에서 0까지
i 진행, 모두 매거, 이렇게 앞의 k개 지점, j개 우체국의 최단로를 넣고, k+1에서 j까지 우체국의 최단로를 넣으면 얻을 수 있습니다!이렇게 하면 이 문제는 해결되지만 극단적일 때 dp[i][0]=sum[0][i], 이것은 초기화해야 한다. 이 문제는 a가 된다!
4

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define inf 0x4f4f4f4f
int dp[320][320],sum[320][320],p[320];
int fmin(int a,int b)
{
    if(a<b)
    return a;
    return b;
}
int main()
{
    int n,m,i,j,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            scanf("%d",&p[i]);
        }
        memset(sum,0,sizeof(sum));

        for(i=0;i<n;i++)
            for(j=i+1;j<n;j++)
            {
                sum[i][j]=sum[i][j-1]+p[j]-p[(i+j)/2];
            }
        for(i=0;i<n;i++)
        {
            dp[i][0]=sum[0][i];
             for(j=1;j<m;j++)
            {
                dp[i][j]=inf;

            }
        }

        for(i=0;i<n;i++)
            for(j=1;j<m;j++)
                for(k=0;k<i;k++)
                {
                    dp[i][j]=fmin(dp[i][j],dp[k][j-1]+sum[k+1][i]);
                }

        printf("%d
",dp[n-1][m-1]);//  ，   0   
    }
    return 0;
}

사각형 최적화 dp 하나 더

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
#define inf 0x4f4f4f4f
int dp[320][320],sum[320][320],p[320],kk[320][320];
int fmin(int a,int b)
{
    if(a<b)
    return a;
    return b;
}
int main()
{
    int n,m,i,j,k;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
        }
        memset(sum,0,sizeof(sum));

        for(i=1;i<=n;i++)
        {
            sum[i][i]=0;
            for(j=i+1;j<=n;j++)
            {
                sum[i][j]=sum[i][j-1]+p[j]-p[(i+j)/2];
            }
        }


        for(i=1;i<=m;i++)
        {

             for(j=1;j<=n;j++)
            {
                dp[i][j]=inf;
            }
        }
         for(i=1;i<=n;i++)
        {
            kk[1][i]=0;
            dp[1][i]=sum[1][i];
        }
        for(i=2;i<=m;i++)
        {
            kk[i][n+1]=n;
            for(j=n;j>i;j--)
            {
                for(k=kk[i-1][j];k<=kk[i][j+1];k++)
                {
                    if(dp[i-1][k]+sum[k+1][j]<dp[i][j])
                    {
                        dp[i][j]=dp[i-1][k]+sum[k+1][j];
                        kk[i][j]=k;
                    }
                }
            }
        }
        printf("%d
",dp[m][n]);
    }
    return 0;
}