#1419. [CSP-J 2022] 上升点列 题解
题目传送门
欢迎大家指出错误并联系这个蒟蒻
更新日志
- 2023-07-07 21:29 文章完成
题目知识点
动态规划（又名 \(\operatorname{DP}\) ）
题意说明
当 \(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\) 排序，使得编号大的点一定是从编号小的点转移过来。
代码+解释
