2022 上升点列 · 方案二二维动态规划

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

状态加上补了几个点，剩的点加在末尾

2022
动态规划

正文

// CSP-J 2022 复赛 T4 · 上升点列（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2022D
//
// 方案二 · 二维 DP：把「补了几个点」也记进状态
// 两个核心观察：
//   1. 从点 h 走到点 i（h 在 i 的左下方），中间要补的整点个数是固定的：
//        t = (x_i - x_h) + (y_i - y_h) - 1
//      补上这 t 个点后，这一段一共贡献 t + 1 个新点。
//   2. 补点不一定要全花在中间 —— 往序列末尾继续加整点同样能拉长序列，
//      而且想加多少就加多少。所以 k 个补点一定会被全部用光，
//      答案 = 「链里用到的给定点个数」 + k。
// 于是定义 dp[i][j] = 以第 i 个点结尾、中间一共补了 j 个点时，
// 链里最多能包含多少个给定点。转移就是枚举前一个点 h：
//   dp[i][j] = max(dp[h][j - t] + 1)，要求 j >= t 且 h 在 i 的左下方。
// 答案 = max(dp[i][j]) + k，其中 j <= k。
// 复杂度 O(n^2 * k)，n = 500、k = 100，约 2.5e7，稳过。

#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][105];

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 best = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = 1;                            // 只有自己一个给定点
            for (int h = 0; h < i; h++) {
                if (p[h].x > p[i].x || p[h].y > p[i].y) continue;
                long long t = (p[i].x - p[h].x) + (p[i].y - p[h].y) - 1;
                if (t > j) continue;                 // 补点不够，接不上
                dp[i][j] = max(dp[i][j], dp[h][j - (int)t] + 1);
            }
            best = max(best, dp[i][j]);
        }
    }
    cout << best + k << "\n";                        // 剩下的补点全加在末尾
    return 0;
}

2022 上升点列 · 方案二 二维动态规划

正文

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

2022 上升点列 · 方案二二维动态规划