递推问题上升点列c++

Question

上升点列（point.cpp）
【题目描述】
在一个二维平面内，给定若干个整数点 (xi , yi)，小明需要从若干点中选出一些个整
数点并组成一个序列，使得序列中任意相邻两点间的欧几里得距离恰好为 1 而且横坐标、
纵坐标值均单调不减， 即 xi+1 − xi = 1, yi+1 = yi 或 yi+1 − yi = 1, xi+1 = xi。请给出满
足条件的序列的最大长度。
3
4
欧几里得距离（欧式距离）:它是在 m 维空间中两个点之间的真实距离。在二维和三维
空间中的欧氏距离的就是两点之间的距离（简单来说就是两点之间直线最短的那段距离）。
二维空间的公式:

曼哈顿距离也称出租车几何，是由十九世纪的赫尔曼·闵可夫斯基在曼哈顿街区研究时
所创词汇，是种使用在几何度量空间的几何学用语，用以标明 两个点在标准坐标系上的绝
对轴距总和。
在平面，曼哈顿距离为：P=|X1-X2|+|Y1-Y2|
【输入格式】
从文件 point.in 中读入数据。
有若干行，第 i 行两个正整数 xi , yi 表示给定的第 i 个点的横纵坐标。
【输出格式】
输出到文件 point.out 中。
输出一个整数表示满足要求的序列的最大长度。
【输入样例 1 】
0 0
1 0
0 1
1 1
4 2
4 1
3 1
2 1
2 2
2 3
1 3
1 4
【输出样例 1】
7
【样例说明】

【输入样例 2】
0 0
1 1
4 5
8 9
10 2
1 3
【输出样例 2】
1
【样例说明】
数据全部为不相连的点，所以最大序列长度为 1。
【输入样例 3】
6 7
1 2
1 3
1 4
1 5
2 5
3 5
4 5
5 5
2 7
3 7
4 7
5 7
5 6
3 2
3 3
4 3
4 4
5 3
【输出样例 3】
11
【数据范围】
对于 50％的数据满足：0<=xi , yi<=10。
对于 l00％的数据满足：0<=xi , yi<=100。数据保证各个点不重

Answer 1

该回答引用自GPT-3.5,由博主GIS_Liu编写：

这个问题可以通过动态规划来解决。首先，我们可以对输入的点按照横坐标和纵坐标进行排序，然后使用动态规划来计算最长上升点列的长度。

具体的解决思路如下：

1. 对输入的点按照横坐标和纵坐标进行排序。
2. 创建一个二维数组 dp，其中 dp[i][j] 表示以第 i 个点为结尾，且以第 j 个点为起始的最长上升点列的长度。
3. 遍历每一个点，计算以当前点为结尾的最长上升点列的长度，即遍历前面的每一个点，找到满足条件的最大长度，并更新 dp[i][j]。
4. 最终结果即为 dp 中的最大值。

以下是这个问题的C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义点结构体
struct Point {
    int x;
    int y;
};

// 比较函数，用于排序
bool compare(Point& a, Point& b) {
    if (a.x == b.x) {
        return a.y < b.y;
    }
    return a.x < b.x;
}

int main() {
    // 读入数据
    vector<Point> points;
    int x, y;
    while (cin >> x >> y) {
        Point p;
        p.x = x;
        p.y = y;
        points.push_back(p);
    }

    // 按照横坐标和纵坐标排序
    sort(points.begin(), points.end(), compare);

    // 动态规划求解最长上升点列的长度
    int n = points.size();
    vector<vector<int>> dp(n, vector<int>(n, 1)); // 初始化为1，每个点至少可以构成长度为1的序列

    int max_length = 1; // 最长上升点列的长度至少为1
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (points[i].x == points[j].x + 1 || points[i].y == points[j].y + 1) {
                dp[i][j] = max(dp[i][j], dp[j][j] + 1);
                max_length = max(max_length, dp[i][j]);
            }
        }
    }

    // 输出结果
    cout << max_length << endl;

    return 0;
}

这段代码首先按照题目要求读入数据，并对输入的点按照横坐标和纵坐标进行排序。然后使用动态规划来计算最长上升点列的长度，最终输出结果即为最长长度。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订