提供一种不一样的做法。
首先将每个点以横坐标为第一关键字，纵坐标为第二关键字排序。
一维的 dp 肯定不够，因为 dp 既要存最多点数，又要保存自由点的点数。
赛时没看 \(k\) 的范围，于是开了一个结构体。
\(dp_i.w\) 表示从当前起点开始且于 \(i\) 点结束的最多的点数，\(dp_i.ned\) 表示达到点数所需的最少的自由点的点数。
从其左下部分的点转移即可。
但如果直接转移，这个 dp 的正确性无法保证，即左部点稀疏而右部点稠密时就会出错。
枚举一个起点 \(st\)，就可以保证 dp 的正确性了。
因为原 dp 出错只能是该点到起点的距离太长，以至于连接后面的稠密点时，自由点不足，此时正解的所选点都在右部的稠密点。
而枚举起点则确定了剩余的所选点只能在右部，相当于枚举了右部点，解决了左疏右密的问题。
时间复杂度：\(\mathcal{O}(n^3)\)
代码：
const int N = 5e2;
int n, k;
struct point {
int x, y;
} a[N + 5];
struct DP {
int w, ned;
} dp[N + 5];
bool cmp(point x, point y) {
return x.x != y.x ? x.x < y.x : x.y < y.y;
}
bool check(int p1, int p2) {
return (a[p1].x > a[p2].x && a[p1].y >= a[p2].y) || (a[p1].x >= a[p2].x && a[p1].y > a[p2].y);
}
int dis(int p1, int p2) {
return abs(a[p1].x - a[p2].x) + abs(a[p1].y - a[p2].y);
}
int main() {
cin >> n >> k;
for(int i = 1; i <= n; i++)
cin >> a[i].x >> a[i].y;
sort(a + 1, a + n + 1, cmp);
int ans = 0;
for(int st = 1; st <= n; st++) {
memset(dp, 0, sizeof(dp));
dp[st].w = 1, dp[st].ned = 0;
for(int i = st + 1; i <= n; i++)
for(int j = st; j < i; j++) {
int nedd = dis(i, j) + dp[j].ned - 1;
if(check(i, j) && nedd <= k && (dp[i].w <= dp[j].w || (dp[i].w == dp[j].w + 1 && nedd < dp[i].ned)))
dp[i].w = dp[j].w + 1, dp[i].ned = nedd;
}
for(int i = 1; i <= n; i++) ans = max(ans, dp[i].w);
}
cout << ans + k << "\n";
return 0;