2004112 2006-08-06 23:32:06 Accepted 1196 C++ 00:00.02 704K St.Crux dis[i][k]表示在前k+1个加油站(0-k)中放入(i+1)个补给站所最小达到的距离和。 cost[i][k]表示从点i到点k所需要的最短距离，当且仅当补给站放在i，k的中点时。 方程是dis[i][k] = min(dis[i - 1][j] + cost[j + 1][k]) i - 1 <= j <k C++的数组下标真是头痛哪 #include <cstdio>#include <string>#include <cmath> int d[201][201], s[201][201], a[201], n, m;#define MX 99999999 int main(){ //freopen("in.txt", "r", stdin); int c = 0; while(scanf("%d %d", &n, &m) && n) {  printf("Chain %d\n", ++ c);  int i, k, j;  for(i = 0; i < n; i ++)  {   scanf("%d", &a[i]);  }  memset(s, 0, sizeof(s));  for(i = 0; i < n; i ++)  {   for(k = i; k < n; k ++)   {    int mid = (i + k) / 2;    for(j = i; j <= k; j ++)    {     s[i][k] += abs(a[j] - a[mid]);    }   }  }  for(i = 0; i < m; i ++)  {   for(k = 0; k < n; k ++)   {    d[i][k] = MX;   }  }  for(i = 0; i < n; i ++)  {   d[0][i] = s[0][i];  }  for(i = 1; i < m; i ++)  {   for(k = i; k < n; k ++)   {    if(k == i)    {     d[i][k] = 0;     continue;    }    for(j = i - 1; j < k; j ++)    {     if(d[i - 1][j] + s[j + 1][k] < d[i][k])      d[i][k] = d[i - 1][j] + s[j + 1][k];    }   }  }   printf("Total distance sum = %d\n", d[m - 1][n - 1]);  printf("\n"); } return 0;}

评论