【poj】1160 Post Office

#include <iostream>
using namespace std;
#include <stdlib.h>

#define MAXNUM 305
#define MAXVAL 0x7f

int mymin(int a, int b) {
    return a<b ? a:b;
}

int main() {
    int v, p;
    int pos[MAXNUM];
    int i, j, k, tmp;
    int only1[MAXNUM][MAXNUM];
    int dis[MAXNUM][MAXNUM];

    while (scanf("%d %d", &v, &p) != EOF) {
        for (i=0; i<v; ++i)
            scanf("%d", &pos[i]);

        for (i=0; i<v; ++i) {
            for (j=i; j<v; ++j) {
                int mid = (i+j)>>1;
                tmp = 0;
                for (k=i; k<=j; ++k) {
                    tmp += abs(pos[k] - pos[mid]);
                }
                only1[i][j] = tmp;
            }
        }

        memset(dis, MAXVAL, sizeof(dis));

        for (i=0; i<v; ++i)
            dis[1][i] = only1[0][i];

        for (i=1; i<p; ++i) {
            for (j=0; j<v; ++j) {
                for (k=0; k<v-j; ++k) {
                    dis[i+1][j+k] = mymin(dis[i][j]+only1[j+1][j+k], dis[i+1][j+k]);
                }
            }
        }

        printf("%d\n", dis[p][v-1]);
    }


    return 0;
}