C :

#include <stdio.h>
#include<math.h>

int INF = ~0U>>1;

int w[305][305]={0};
int dp[305][35];
int a[305],V,P;

void Init(int a[],int n)
{
	int i,j;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            w[i][j] = w[i][j-1] + a[j] - a[(i+j)>>1];
}

int min(int a,int b)
{
	if(a<b)
		return a;
	else
		return b;
}
int Work()
{
	int i,j,k;
    for(i=1;i<=V;i++)
    {
        dp[i][i] = 0;
        dp[i][1] = w[1][i];
    }
    for(j=2;j<=P;j++)
    {
        for(i=j+1;i<=V;i++)
        {
            dp[i][j] = INF;
            for(k=j-1;k<i;k++)
                dp[i][j] = min( dp[i][j] , dp[k][j-1] + w[k+1][i]);
        }
    }
    return dp[V][P];
}
int main()
{
	int i,tcase;
	scanf("%d",&tcase);
	while(tcase--)
	{
		scanf("%d%d",&V,&P);
        for(i=1;i<=V;i++)
            scanf("%d",&a[i]);
        Init(a,V);
        printf("%d\n",Work());
    }
    return 0;
}

C++ :

#include <iostream>
#include <string.h>
using namespace std;
int cost[302][302];
int res[302][302];
int village[302];
inline int myabs(int a)
{return a>0?a:-a;}

int main(){
    int V,P,mid;
    int tcase;
    cin>>tcase;
    while(tcase--){
    cin>>V>>P;
    for (int i=1;i<=V;i++)
        cin>>village[i];
    //cost 初始化
    memset(res,0,sizeof(res));
    memset(cost,0,sizeof(cost));
    for (int i=1;i<=V;i++){
        for (int j=i;j<=V;j++){
            mid=(i+j)>>1;
            for (int k=i;k<=j;k++)
                cost[i][j] +=myabs(village[mid]-village[k]);
        }
    }
    //res[i][j] 表示前i个邮局覆盖前j个村庄的最小代价
    for (int i=1;i<=V;i++)
        res[1][i]=cost[1][i];
    for (int i=2;i<=P;i++){
        for (int j=1;j<=V;j++){
            for (int k=1;k+j<=V;k++){
                if(res[i][j+k]>res[i-1][j]+cost[j+1][j+k] || res[i][j+k]==0)
                    res[i][j+k]=res[i-1][j]+cost[j+1][j+k];
            }
        }
    }
    cout<<res[P][V]<<endl;
    }
    return 0;
}