1 条题解
-
0
题目分析
20 分
暴力搜索即可。
40 分
需要挖掘一些性质,考虑到最终留下来的序列是原序列的一个子序列。
那么一个合法的子序列需要满足什么性质。
假设这个子序列是 ,该子序列合法的充要条件是:
- ,。
- ,。
- ,或者 。
这个条件是显然的,因为如果区间 的最小值比两边留下来的数都小,那么这个数肯定删除不了。
知道这个就好搞了,暴力搜索枚举即可,复杂度是指数级的。
60 分
注意到这个是 dp 的,设 表示选到了 (强制选 )的最长合法的子序列长度。
转移是 easy 的,枚举上一次的转移点,合法条件暴力 check 即可,时间复杂度是三方的。
80 分
每次判断合法没必要暴力 check,知道这个区间的最小值就行了,于是从后往前维护最小值即可。
时间复杂度是两方的。
正解
考虑优化,设 表示 左边第一个比它小的数的位置。
枚举上一次的转移点 。
- ,注意到这样的转移点一定是合法的,前缀和优化即可。
- ,如果 ,那么这个转移点显然不合法,否则需要满足 ,即所有后缀最小值的位置都是合法的转移点,维护一个 即可。
时间复杂度 。
- 1
信息
- ID
- 71
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者