1 条题解
-
0
题目分析
数据点 1
每个位置只有一种取值,直接使用 LIS 算法即可。
数据点 2~3
考虑 DP,设 为确定了前 个数, 确定为 的 LIS。
那么有转移方程:。
数据点 4~6
考虑开一个数据结构维护转移,在求出所有 后,往这个数据结构里面加二元对 ,只要每次在这个数据结构里面选转移,就满足了 的限制。
对于第二维的限制,发现这个数据结构需要支持:
- 插入一个二元组 。
- 查询 的最大 。
使用线段树即可。
数据点 7~10
由题意易知 ,而对于相同的 DP 值, 越小一定越优秀,于是我们可以让这个数据结构时刻只存在 个转移。
接下来让数据结构中所有值按照 排序,并且对 的 个取值进行排序,然后进行双指针即可完成转移。
于是就在 的时间复杂度内解决了该问题。
- 1
信息
- ID
- 126
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者