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;
}

评论