我不知道优化，我只知道最暴力的方法，O(V^3),居然100ms不到的过了
设DP[i][j][k]表示考虑前i个小镇，放了j个邮局，最后一个邮局的所在城镇编号为k的k以前的所有的城镇距离最近的邮局的最小距离和（TM自己给自己搞了个这么绕的状态。。）
那么有DP[i][j][i] = MIN{DP[i-1][j-1][k] + dis[k][i]}其中k<i
DP[i][j][k] = DP[i-1][j][k]
其中，dis[k][i]表示[k, i]这个区间里的所有城镇距离 邮局k 和 邮局i 的最小值的和，即：
dis[i][j] = sum{ MIN(x[k]-x[i], x[j]-x[k]) } i<=k<=j
考虑边界条件，对于DP[i][j][k],由于如果前i个城镇一个都不放，那么k取任意值都是不合法的（因为我是这么表示状态的2333333..），所以对于任意的i，先算一边j=1的情况，即DP[i][1][k] = dis[0][k],默认的x[0] = -INF
最后的答案就是： MIN{DP[V][P][k] + dis[k][V]} P <=k<=V
其他的按照上面的思路敲就是了，然后我就愉快的提交了,TM居然告诉我内存超了300 × 300 × 30 啊，怎么会超！！！TM内存只给了10000,没办法就只好将第一维大小压缩到2(因为当前的i只与i-1有关。。)
79ms，O(V^3)，我愉快的笑了
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 100000000
#define inf (-((LL)1<<40))
#define lson k<<1, L, mid
#define rson k<<1|1, mid+1, R
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a, b) memset(a, b, sizeof(a))
#define FOPENIN(IN) freopen(IN, "r", stdin)
#define FOPENOUT(OUT) freopen(OUT, "w", stdout)
template<class T> T CMP_MIN ( T a, T b ) { return a < b; }
template<class T> T CMP_MAX ( T a, T b ) { return a > b; }
template<class T> T MAX ( T a, T b ) { return a > b ? a : b; }
template<class T> T MIN ( T a, T b ) { return a < b ? a : b; }
template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; }
template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b; }
template<class T> T SWAP( T& a, T& b ) { T t = a; a = b; b = t; } //typedef __int64 LL;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
const double eps = 1e-; int V, P;
int x[], DP[][][];
int dis[][], pre[]; void initDis()
{
mem0(dis);mem0(pre);
for(int i=;i<=V;i++)
for(int j=i;j<=V;j++)
for(int k=i;k<=j;k++)
dis[i][j] += MIN(x[k]-x[i], x[j]-x[k]);
for(int i=;i<=V;i++)for(int j=i;j>=;j--)
pre[i] += x[i] - x[j];
} int main()
{
//FOPENIN ( "in.txt" );
//FOPENOUT("out.txt");
while(~scanf("%d %d", &V, &P))
{
for(int i=;i<=V;i++)
scanf("%d", &x[i]);
initDis();
for(int i=;i<;i++)
for(int j=;j<=MIN(i,P);j++)
for(int k=;k<=i;k++){
DP[i][j][k] = INF;
}
int now = ;
for(int i=;i<=V;i++)
{
now = !now;
int s = ;
for(int j=;j<=i;j++) DP[now][][j] = pre[j];
for(int j=;j<=MIN(i, P); j++)
{
DP[now][j][i] = INF;
for(int k=j-;k<i;k++)if(DP[!now][j-][k] != INF)
{
DP[now][j][i] = MIN(DP[now][j][i], DP[now][j-][k] + dis[k][i]);
}
for(int k=j;k<i;k++) DP[now][j][k] = DP[!now][j][k];
}
}
int ans = INF;
for(int k=P;k<=V;k++)if(DP[now][P][k] != INF)
{
int s = ;
for(int j = k + ; j <= V; j ++ ) s += x[j] - x[k];
ans = MIN(ans, DP[now][P][k] + s);
}
printf("%d\n", ans);
}
return ;
}