poj 1160 Post Office

/*
* poj 1160 Post Office
* antsmall
* 2010-09-26
*/

#include<iostream>
using namespace std;

int dist[301][301];
int x[301];
int pv[31][301];
const int MIN_INT = 100000000;

void getDist(int v) {
memset(dist, 0, sizeof(dist));
for(int i = 1; i < v; i++) {
   for(int j = i+1; j <= v;j++) {
    int mid = (i+j)/2;
    for(int k = i; k <= j; k++) {
     dist[i][j] += abs(x[k] - x[mid]);
    }
   }
}
}

int solve(int v, int p) {
memset(pv, 0, sizeof(pv));
for(int i = 1; i <= v; i++) {
   pv[1][i] = dist[1][i];
}
  
for(int i = 2; i <= p; i++) {
   for(int j = i + 1; j <= v; j++) {
    int min = MIN_INT;
    for(int k = i - 1; k < j; k++) {
     int tmp = pv[i-1][k] + dist[k+1][j];
     if(tmp < min)
      min = tmp;
    } 
    pv[i][j] = min;
   } 
}

return pv[p][v];
}

int main() {
int v, p;

scanf("%d%d", &v, &p);
for(int i = 1; i <= v; i++) {
   scanf("%d", &x[i]);
}

getDist(v);
printf("%d\n", solve(v,p));

//system("pause");
return 0;
}