这是一道DP的题，用w[i][j]代表用一个邮局覆盖第i个到第j个点所得到的最小距离和。

用f[i][j]代表用前i个邮局覆盖前j个点所得到的最小距离和。然后根据这里我们可以推

出状态转移方程为：f[i][j] = min( f[i][j ] , f[i - 1][k] + w[k + 1][j] )  ( k < j).

/*Accepted    528K    79MS    C++    1195B    2012-08-07 14:23:15*/#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int MAXP = 35, MAXV = 305, INF = 0x3f3f3f3f;int a[MAXV], f[MAXP][MAXV], w[MAXV][MAXV];int p, v;void init(){    int i, j, k, m;    for(i = 1; i <= v; i ++)        scanf("%d", &a[i]);    for(i = 1; i <= v; i ++)    {        for(j = i; j <= v; j ++)        {            w[i][j] = 0;            m = i + j >> 1;            for(k = i; k <= j; k ++)            {                if(k <= m)                    w[i][j] += (a[m] - a[k]);                if(k > m)                    w[i][j] += (a[k] - a[m]);            }        }    }    for(i = 1; i <= p; i ++)        for(j = 1; j <= v; j ++)            f[i][j] = INF;    for(j = 1; j <= v; j ++)        f[1][j] = w[1][j];}void dp(){    int i, j, k;    for(i = 2; i <= p; i ++)        for(j = 2; j <= v; j ++)            for(k = i; k <= j; k ++)                f[i][j] = min(f[i][j], f[i - 1][k] + w[k + 1][j]);}int main(){    while(scanf("%d%d", &v, &p) == 2)    {        init();        dp();        printf("%d\n", f[p][v]);    }    return 0;}