设 $f_{i,j}$ 为 $1\sim i$ 的检查站中，通过了第 $i$ 个，跳过了 $j$ 个所要跑的最短距离。则有

$$f_{i,j}=\min\limits_{0\le l\le\min(i-2,j)}\{f_{i-l-1,j-l}+|x_i-x_{i-l-1}|+|y_i-y_{i-l-1}|\} $$

解释一下，$l$ 表示上一个通过的检查站到当前检查站之间跳过了几个，所以上一个通过的检查站为 $i-l-1$。因为 $1\sim i$ 之间最多只有 $i-2$ 个检查站可以跳过，所以 $l\le i-2$，又因为 $f_{i,j}$ 的定义，最多只能跳 $j$ 个，故 $l\le j$。综上所述，有 $0\le l\le\min(i-2,j)$。

花括号里面的转移式中，$f_{i-l-1,j-l}$ 表示上一个通过的检查站及之前的最优策略，总共要跳过 $j$ 个，当前这一段跳过了 $l$ 个，所以之前的总共跳过了 $j-l$ 个。右边的就是当前段的曼哈顿距离（转移代价）。

按此式 dp 即可。总时间复杂度为 $O(nk^2)$。

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int x[505], y[505], f[505][505];
inline int abs(int a) {
    return a > 0 ? a : -a;
}
inline int dist(int a, int b) {
    return abs(x[a] - x[b]) + abs(y[a] - y[b]);
}
int main() {
    memset(f, 63, sizeof(f));
    f[1][0] = 0;
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &x[i], &y[i]);
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= k; j++)
            for (int l = 0; l <= j && l < i - 1; l++)
                f[i][j] = min(f[i][j], f[i - l - 1][j - l] + dist(i, i - l - 1));
    printf("%d\n", f[n][k]);
    return 0;
}