思路与算法

按坐标排序，DP记录以某原有点结尾并消耗若干新增点时最多纳入的原有点数。两个可单调连接的点之间至少补曼哈顿距离减1个点，枚举前驱和预算转移。

正确性说明

在任意最优单位步序列中，按出现顺序考虑原有点，相邻两原有点需补的空位数为坐标距离减1；若途经其他原有点可纳入该链节省预算。转移覆盖所有这种链。剩余新增点总可在尾端继续向右或向上追加，所以最大原有点数加k就是最优总长度。

复杂度

O(n²k+n log n)时间、O(nk)空间，含排序和DP负无穷初始化。

易错点

新增整点不受原坐标范围限制，可以延长序列；不可把严格二维上升当成两个坐标都必须增加，某一坐标可以相等。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<pair<long long, long long>> a(n);
    for (auto &p : a)
        cin >> p.first >> p.second;
    sort(a.begin(), a.end());
    vector<vector<int>> f(n, vector<int>(k + 1, -1000000));
    int ans = 1 + k;
    for (int i = 0; i < n; i++) {
        f[i][0] = 1;
        for (int p = 0; p < i; p++)
            if (a[p].second <= a[i].second) {
                long long gap = a[i].first - a[p].first + a[i].second - a[p].second - 1;
                if (gap <= k)
                    for (int j = gap; j <= k; j++)
                        f[i][j] = max(f[i][j], f[p][j - gap] + 1);
            }
        for (int j = 0; j <= k; j++)
            ans = max(ans, f[i][j] + k);
    }
    cout << ans << "\n";
}