在一个二维平面内，给定 n 个整数点 (xi, yi)，此外你还可以自由添加 k 个整数点。 你在自由添加 k 个点后，还需要从 n + k 个点中选出若干个整数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且横坐标、纵坐标值均单调不减， 即 xi+1 − xi = 1, yi+1 = yi 或 yi+1− yi = 1, xi+1 = xi。请给出满足条件的序列的最大长 度。 输入格式 第一行两个正整数 n, k 分别表示给定的整点个数、可自由添加的整点个数。接下来 n 行，第 i 行两个正整数xi,yi , 表示给定的第 i 个点的横纵坐标。 输出格式 输出一个整数表示满足要求的序列的最大长度。

本题是一道组合计数问题，可以通过枚举每个点作为序列的起点，并在其右边或下边的点中选择满足条件的点来确定序列。在选择满足条件的点时，我们可以使用动态规划的思想，维护一个二维数组 dp，其中 dp[i][j] 表示从点 (i, j) 开始向右或向下选择点所能得到的最长序列长度。如果点 (i, j) 本身已经被选中，则 dp[i][j] 的值为 1，否则 dp[i][j] 的值为该点右边或下边的满足条件的点所能得到的最长序列长度加 1。最终答案即为所有 dp 数组中的最大值。

以下是 Python 实现代码：

n, k = map(int, input().split())

points = set()
for i in range(n):
    x, y = map(int, input().split())
    points.add((x, y))

dp = [[0] * (max(p[1] for p in points) + 2) for _ in range(max(p[0] for p in points) + 2)]
for x, y in points:
    dp[x][y] = 1

for i in range(max(p[0] for p in points), 0, -1):
    for j in range(max(p[1] for p in points), 0, -1):
        if (i, j) not in points:
            dp[i][j] = max(dp[i+1][j], dp[i][j+1])

ans = max(max(row) for row in dp)
print(ans)

以下是 C++ 实现代码：

#include <iostream>
#include <set>
#include <vector>

using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    set<pair<int, int>> points;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        points.insert({x, y});
    }

    int max_x = max_element(points.begin(), points.end(), [](auto &a, auto &b) { return a.first < b.first; })->first;
    int max_y = max_element(points.begin(), points.end(), [](auto &a, auto &b) { return a.second < b.second; })->second;
    vector<vector<int>> dp(max_x + 2, vector<int>(max_y + 2));
    for (const auto &p : points)
        dp[p.first][p.second] = 1;

    for (int i = max_x; i >= 1; i--)
    {
        for (int j = max_y; j >= 1; j--)
        {
            if (!points.count({i, j}))
            {
                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
    }

    int ans = *max_element(dp[1].begin() + 1, dp[1].end());
    cout << ans << endl;

    return 0;
}