我定义了一个二维数组dp[i][j]，表示前j个位置，修建了i个邮局。所以推导出的状态转移方程为：
dp[i][j] = min{dp[i][j-1]+第j个位置到第i个邮箱位置的差，dp[i-1][k] + 第j个位置到第k+1个位置的差}，实际上花括号里，左边代表第i个邮箱不在第j个位置上，而右边代表第i个邮箱在第j个位置上，为了能够确定dp[i][j]中第i个邮箱建立的位置，我用一个chosen[i][j]记录下来，表示前j个位置中，第i个邮箱建立的位置，这样就可以直接计算第j个位置与第i个邮箱位置的差。。此外，如果第i个邮箱有多个位置都满足要求的话，那么尽可能地往右边建。。
但是一直是WA。。。没有想通到底是哪里出了问题。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 3300;
const int inf = 0x3fff;
int n,m,pos[maxn],dp[33][maxn],chosen[33][maxn];

int main()
{	
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(dp[0],0,sizeof(dp[0]));
		memset(chosen,0,sizeof(chosen));
		for(int i = 1; i <= n; i++)
			scanf("%d",&pos[i]);
		for(int j = 1; j <= n; j++)
			for(int k = j-1; k >= 1; k--)//dp[0][j]不起作用就把它用作前j-1个位置到第j个位置差的总和。。方便后面计算。。
				dp[0][j] += pos[j]-pos[k];
		for(int i = 1; i <= m; i++)
			for(int j = 1; j<= n; j++)
				dp[i][j] = inf;
		for(int i = 1; i <= m; i++) 
		{
			dp[i][i] = 0;
			chosen[i][i] = i;
		}
		for(int j = 2; j <= n; j++)
		{
			int sum = 0, choose = 0;
			dp[1][j] = dp[0][j];
			for(int k = j-1; k >= 1; k--)
			{
				sum = 0;
				for(int t = k+1; t <= j; t++) sum += pos[t] - pos[k];
				if((dp[0][k]+sum < dp[1][j]) || ((dp[0][k]+sum == dp[1][j]) && (choose == 0))) //保证多个情况满足时尽可能靠右。。
				{
					dp[1][j] = dp[0][k] + sum;
					chosen[1][j] = k;
					choose = 1;
				}
			}
		}
		for(int i = 2; i <= m; i++)
			for(int j = i+1; j <= n; j++)
			{
				if(dp[i][j-1] != inf)
				{
					dp[i][j] = dp[i][j-1] + pos[j] - pos[chosen[i][j-1]];
					chosen[i][j] = chosen[i][j-1];
				}
				int sum = 0,choose = 0;
				for(int k = j-1; k >= i; k--)
				{
					if(dp[i-1][k] != inf)
					{
						if((dp[i-1][k] + sum < dp[i][j]) || ((dp[i-1][k] + sum == dp[i][j]) && (choose == 0)))//理由同上
						{
							dp[i][j] = dp[i-1][k] + sum;
							chosen[i][j] = j;
							choose = 1;
						}
					}
					sum += pos[j] - pos[k];
				}
			}
		printf("%d\n",dp[m][n]);
	}
	return 0;
}