2022 上升点列 · 方案一先只考虑不加点

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1298 字

相邻点必须紧挨着，做一次类 LIS 的 DP

2022
动态规划

正文

// CSP-J 2022 复赛 T4 · 上升点列
// 原题：https://oj.yecheng.tv/p/CSPJ2022D
// 题意：平面上给定 n 个整点，另外允许自由添加 k 个整点。
// 要从这些点里选出一条序列，使得相邻两点的距离恰好为 1、且横纵坐标都单调不减
// （也就是每一步只能向右或向上走一格），求序列的最大长度。
//
// 方案一 · 先只考虑 k = 0（相邻给定点必须紧挨着）
// 两点 (x1,y1) 到 (x2,y2) 能直接相连，当且仅当 x2 >= x1、y2 >= y1
// 且 (x2 - x1) + (y2 - y1) == 1。
// 于是把所有点按 (x, y) 排序，做一次最长上升子序列式的 DP：
//   dp[i] = 以第 i 个点结尾的最长链长度
//   dp[i] = max(1, dp[h] + 1)  对一切能和 i 直接相连的 h < i
// 这一版对应 k = 0 的那批测试点，想拿满分请看法二。

#include <bits/stdc++.h>
using namespace std;

struct Point {
    long long x, y;
};

bool cmpPoint(const Point& A, const Point& B) {
    if (A.x != B.x) return A.x < B.x;
    return A.y < B.y;
}

int dp[505];

int main() {
    freopen("point.in", "r", stdin);
    freopen("point.out", "w", stdout);

    int n, k;
    cin >> n >> k;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
    sort(p.begin(), p.end(), cmpPoint);

    int ans = 1;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int h = 0; h < i; h++) {
            long long step = (p[i].x - p[h].x) + (p[i].y - p[h].y);
            if (p[h].x <= p[i].x && p[h].y <= p[i].y && step == 1) {
                dp[i] = max(dp[i], dp[h] + 1);
            }
        }
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
    return 0;
}

2022 上升点列 · 方案一 先只考虑不加点

正文

CSP-J 标程 · 复赛真题的其它内容

2022 上升点列 · 方案一先只考虑不加点