Poj 1160 Post Office(DP 간단한 문제)

1379 단어
n개 마을에 p개의 우체국을 건설하고 가장 좋은 건설 방안을 구하여 각 마을이 가장 가까운 우체국까지의 거리와 가장 짧고 수출이 가장 짧은 거리를 확보한다.
먼저 n개 마을에 우체국을 건설하는 가장 좋은 방안을 추론해 보면 아래 그림을 그리면 이해하기 쉽다.
여러 우체국을 풀 수 있는 최선의 방안을 다시 한 번 추측해 보고 구체적으로 주석을 보아라.
/*
//k 1   i-1   
dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k+1][i]);

           。
sum[i][j]=sum[i][j-1]+p[j]-p[(i+j)/2];
*/

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int sum[305][305];      // i j            
int p[305];
int dp[305][305];       // i    j        

int main()
{
    int n,k;
    while(~scanf("%d%d",&n,&k))
    {
        memset(dp,0x3f,sizeof(dp));
        memset(sum,0,sizeof(sum));
        p[0]=0;

        for(int i=1;i<=n;i++)
        {
            scanf("%d",&p[i]);
        }

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

        for(int j=2;j<=k;j++)
        {
            for(int i=j+1;i<=n;i++)
            {
                for(int k=1;k<i;k++)
                {
                    dp[i][j]=min(dp[i][j],dp[k][j-1]+sum[k+1][i]);
                }
            }
        }
        printf("%d
",dp[n][k]); } return 0; }

좋은 웹페이지 즐겨찾기