1楼
本人刚学DP,想问问大家我的代码那错了,谢谢了
题意:给定V(1 <= V <= 300)个村庄的坐标(升序排列)。在V个村庄中建P个邮局。求 the sum of all distances between each village and its nearest post office。(详见POJ1160)
代码如下:
#include<stdio.h>
#include<math.h>
#define mount 1000
int main(void){
int minlen[mount], a[mount]; int i, j, k, P, V, sum, t = 1000000000, c;
scanf("%d%d", &V, &P);
for(i = 0; i < V; i++)//先把每个村庄到邮局的距离附很大的初值//
minlen[i] = 1000000000;
for(i = 0; i < V; i++)
scanf("%d", &a[i]);
for(k = P; k >= 1; k--){
for(j = 0; j < V; j++){//当安置一个邮局是,找到距离和最小的位置//
sum = 0;
for(i = 0; i < V; i++){
if(abs(a[i] - a[j]) > minlen[i])
sum += minlen[i];
else sum += abs(a[i] - a[j]);
}
if(sum < t){
t = sum;
c = j;//记下距离和最小位置的坐标//
}
}
for(j = 0; j < V; j++)//把每个村庄到临近邮局的最短距离记下//
if(abs(a[c] - a[j]) < minlen[j])
minlen[j] = abs(a[c] - a[j]);
}
sum = 0;
for(i = 0; i < V; i++)
sum += minlen[i];
printf("%d\n", sum);
return 0;
}