POJ 1160
题意
有n个村庄，要求选其中的p个建立邮局，求最小的距离。
思路
#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;
}
