POJ 1160 Post Office （动态规划）

Description

Input

Output

Sample Input

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

Sample Output

9

Source

题目大意：

有n个村庄，m个邮局，每个村庄的位置坐标告诉你，现在要将m个邮局设立在这n个村庄里面，问你最小花费是多少？花费为每个村庄到最近的邮局的距离和。

解题思路：

dp[i][j] 记录 i个邮局 j个村庄的最小花费，cost[k+1][j]，记录在k+1号村庄到 j 号村庄设立一个邮局的最小花费。

那么：dp[i][j]=min { dp[i][k]+cost[k+1][j] }

最后输出dp[m][n]即可。

但是在k+1号村庄到 j 号村庄设立一个邮局的最小花费是多少呢？答案：中位数，设置在中间那个村庄即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn=310;
const int maxm=40;
int cost[maxn][maxn],dp[maxm][maxn],a[maxn];
int n,m,s[maxn][maxn];

void input(){
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            cost[i][j]=0;
            int mid=(i+j)/2;
            for(int k=i;k<=j;k++){
                cost[i][j]+=abs(a[k]-a[mid]);
            }
        }
    }
}

int DP(int c,int r){
    if(dp[c][r]!=-1) return dp[c][r];
    if(c==1) return cost[1][r];
    int ans=(1<<30);
    for(int i=1;i<r;i++){
        int tmp=DP(c-1,i)+cost[i+1][r];
        if(tmp<ans) ans=tmp;
    }
    return dp[c][r]=ans;
}

void solve(){
    cout<<DP(m,n)<<endl;
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        input();
        solve();
    }
    return 0;
}

POJ 1160 Post Office （动态规划）,布布扣,bubuko.com

POJ 1160 Post Office （动态规划）

原文：http://blog.csdn.net/a1061747415/article/details/37594433