网上的解法：
#include<stdio.h>
const int MAX=3000000;
int v,p_o,dis[301];
int opt[31][301],cost[301][301];
int main()
{
    scanf("%d%d",&v,&p_o);
    int i,j,k;
    for(i=1;i<=v;i++) scanf("%d",&dis[i]);
    for(i=1;i<=v;i++)
       for(j=i;j<=v;j++)
       {
          cost[i][j]=0;
          int mid=(i+j)/2;
          for(k=i;k<=j;k++)
             cost[i][j]+=(dis[mid]-dis[k])>0?dis[mid]-dis[k]:dis[k]-dis[mid];
       }
    for(i=0;i<=p_o;i++)
       for(j=0;j<=v;j++) opt[i][j]=MAX;
    opt[0][0]=0;
    for(i=0;i<=p_o;i++)
       for(j=0;j<=v;j++)
       {
           for(k=1;k+j<=v;k++)
           {
              if(opt[i+1][j+k]>opt[i][j]+cost[j+1][j+k])
                 opt[i+1][j+k]=opt[i][j]+cost[j+1][j+k];
           }
       }
    printf("%d\n",opt[p_o][v]);
    return 0;
}
我的解法 不过代码有点丑：
#include<iostream>
#include<cstdio>
using namespace std;
const int lmax=301;
const int Lmax=3000000;
int cost[lmax][lmax],min_sum[lmax][lmax];
int d[lmax];
int main()
{
	int v,postoffice,i,j,k,middle;
	scanf("%d%d",&v,&postoffice);
	for(i=1;i<=v;i++)scanf("%d",&d[i]);
	for(i=1;i<v;i++)
	{
		for(j=i;j<=v;j++)
		{
			cost[i][j]=0;
			if(i==j)continue;
			middle=(i+j)/2;
			for(k=i;k<=j;k++)
			{
				cost[i][j]+=(d[k]-d[middle])>0?d[k]-d[middle]:d[middle]-d[k];
			}
		}
	}
	for(i=1;i<=postoffice;i++)
	{
		for(j=1;j<=v;j++)
		{
			min_sum[i][j]=Lmax;
		}
	}
	for(i=1;i<=v;i++)
	{
		min_sum[1][i]=cost[1][i];
	}
	for(i=2;i<=postoffice;i++)
	{
		for(j=1;j<=v;j++)
		{
			for(k=1;k<j;k++)
			{
				if(min_sum[i][j]>min_sum[i-1][k]+cost[k+1][j])
                        {
                        	min_sum[i][j]=min_sum[i-1][k]+cost[k+1][j];
                        }
			}
		}
	}
	printf("%d\n",min_sum[postoffice][v]);
	return 0;
}