#1419. [CSP-J 2022] 上升点列 题解

本文章的访问次数为次。

Part 1 提示

• 题目传送门
• 欢迎大家指出错误并私信这个蒟蒻
• 欢迎大家在下方评论区写出自己的疑问（记得 @ 这个蒟蒻）
• 本文已同步至学校网站、博客园。

Part 2 背景

本文是这个蒟蒻学校的第五篇题解，欢迎大家来看。

Part 3 更新日志

• 2023-07-07 21:29 文章完成
• 2023-07-07 21:29 文章同步至学校网站
• 2023-08-18 20:24 文章同步至博客园

Part 4 题目知识点

动态规划（\(\operatorname{DP}\) ）

Part 5 题意说明

当 \(k=0\) 且 \(x_i\)，\(y_i\) 值域不大时，这题其实是一个十分简单的 \(\operatorname{DP}\)，就类似于数字三角形。直接记 \(dp(x,y)\) 为 「以 \((x,y)\) 为终点，最长合法序列的长度」。则对于所有（已经存在的）整点，有：

\(dp(x,y)=\) \(\max\begin{Bmatrix}{dp(x - 1, y), dp(x, y - 1)}\end{Bmatrix}+1\)

但是我们可以发现，当 \(x_i\)，\(y_i\) 值域比较大时就不行了，所以我们需要进行优化，可以考虑记 \(dp(n)\) 表示 「以 \(n\) 号点结尾的合法序列，最长能有多长」。

\(dp(n)=\) \(\max_{i→n}\begin{Bmatrix}{dp(i) + 1}\end{Bmatrix}\)

不会存在环状结构（因为合法序列必须向右、上方发展），所以把刚刚的 \(\operatorname{DP}\) 改造一下，就是本题的正解了：记 \(dp(n,k)\) 表示 「以 n 号点结尾，已经使用掉了 k 个自由点，获得的收益」。

\(dp(n,k)=\) \(\max_{i→n}\begin{Bmatrix}{dp(i, k − cost) + cost + 1}\end{Bmatrix}\)

实现细节：本题的求值顺序值得注意，合法路径可能形如 \(P_1 → P_3 → P_2\)。有两种解决方法：

• 记忆化搜索（记忆化搜索最擅长解决求值顺序混乱的 \(\operatorname{DP}\)）。
• 预先按 \(x,y\) 排序，使得编号大的点一定是从编号小的点转移过来。

Part 6 代码

// #1419. [CSP-J 2022] 上升点列
// code by:st20250113
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 510;

int n, k, tx, ty, ans;
int x[MAXN], y[MAXN];

vector<pair<int, int>> v;

void inp()
{
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &tx, &ty);
        v.push_back(make_pair(tx, ty));
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++)
    {
        x[i + 1] = v[i].first;
        y[i + 1] = v[i].second;
    }
}

int dis(int a, int b)
{ // a -> b 的距离
    if (x[a] > x[b])
    {
        return 23333333;
    }
    if (y[a] > y[b])
    {
        return 23333333;
    }
    return x[b] - x[a] + y[b] - y[a] - 1;
}

int dp[MAXN][110];

void dp_forward(int p, int c)
{ // 以 p 为终止点，目前已经使用了 c 个自由点
    // dp[p][c] -> dp[t][c+dis(p, t)] where t 可转移
    if (dp[p][c] == -1)
    { // 不可达状态
        return;
    }
    for (int t = p + 1; t <= n; t++)
    {
        int dis_pt = dis(p, t);
        if (c + dis_pt <= k)
        {
            dp[t][c + dis_pt] = max(dp[t][c + dis_pt], dp[p][c] + dis_pt + 1);
        }
    }
}

void work()
{
    memset(dp, -1, sizeof(dp));
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = 1;
    }
    for (int p = 1; p <= n; p++)
    {
        for (int c = 0; c <= k; c++)
        {
            dp_forward(p, c);
        }
    }
    for (int p = 1; p <= n; p++)
    {
        for (int c = 0; c <= k; c++)
        {
            if (dp[p][c] != -1)
            {
                ans = max(ans, dp[p][c] + k - c);
            }
        }
    }
    cout << ans << endl;
}

int main()
{
    inp();
    work();
    return 0;
}