POJ 1160

题意

有n个村庄，要求选其中的p个建立邮局，求最小的距离。

思路

学习kedebug博客思路代码

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 310;
const int IFNS = 0x3fffffff;

int dp[MAXN][MAXN],cost[MAXN][MAXN],x[MAXN];
int vil,office;

int calccost(int i, int j){
    int ans = 0;
    while(i<j){
        ans += x[j] - x[i];
        i++,j--;
    }
    return ans;
}

int workout(){
    for(int i=0;i<office;i++){
        for(int j = i;j<= vil;j++){
            dp[0][0] = 0;

        }
    }

    for(int i=1;i<=office;i++){
        for(int j=i;j<=vil;j++){
            for(int k=0;k<j;k++)
                dp[i][j] = min(dp[i][j],dp[i-1][k]+cost[k+1][j]);
        }
    }
    return dp[office][vil];
}

int main(){
    // 输入村庄数，邮局 还有村庄的位置 
    while(~scanf("%d%d",&vil,&office)){
        x[0] = 0;
        for(int i=0;i<vil;i++){
            scanf("%d",&x[i]);
        }

        for(int i=1;i<=vil;i++)
            for (int j = i; j <= vil; ++j)
                cost[i][j] = calccost(i,j);//计算两个村庄之间所有村庄的距离之和

            
        printf("%d\n",workout());   
    }
    return 0;
}