动态规划吧 关注:92贴子:274
  • 2回复贴,共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;
}



1楼2011-04-28 10:38回复
    ...


    2楼2011-07-24 09:48
    回复
      P 表示无力


      IP属地:北京3楼2012-09-24 21:05
      回复