题目大意
共有两问
- 求最长不升子序列
- 求最少能分为几个不升子序列
Sol
原数据是 \(1e4\) 的,所以先考虑 \(O(n^2)\) 做法。
- 第一问
容易发现,这跟我们求最长不降子序列是一样的
所以我们直接设状态为 \(dp_i\) 表示前 \(i\) 个数中所能得到的最长不升子序列长度
转移如下:
\[dp_i= \left\{ \begin{array}{l}1 \\dp_j+1 & j<i\ 且\ h_j\geq h_i\end{array}\right.
\]
- 第二问
我们可以直接维护一个数组 \(g\) 表示到第 \(i\) 个最少需要的几个拦截装置的目前高度
每次扫一遍 \(g\) 找到最小的 \(g_j\geq h_i\) 把 \(g_j\) 更新为 \(h_i\)
总体空间复杂度 \(O(n)\),时间复杂度 \(O(n^2)\)。
这样可以在原数据拿到 \(100\) 分,但为了拿到 \(200\) 分我们考虑一下 \(O(n\log n)\) 做法。
- 第一问
我们主要的复杂度瓶颈在于找到最大的 \(dp_j\),所以考虑从这方面优化。
容易发现,对于不同的长度,长度越长的最后的数字一定越小(短的在拼上一个小的就会变成长的)
所以当长度递增时,每个长度结尾数的最大值一定单调不增,就满足了二分性质。
再开一个数组 \(f_i\) 表示当长度为 \(i\) 是所能取得的最大结尾数字,在状态转移时二分一个最小的 \(f_j\geq h_i\)
这时的答案就是 \(i+1\) - 第二问
有一个比较特殊的性质:如果按照上面的方式更新 \(g\) 数组,其实其中的元素是有单调不减性质的
例如我们找到一个最小的 \(g_j\geq h_i\),更新后由于 \(g_{j-1}< h_i=g_j\leq g_{j+1}\),不会破坏单调性
所以直接改成二分就可以了,由于lower_bound
返回的是指针,可以直接*lower_bound(...)=h[i]
总体空间复杂度 \(O(n)\),时间复杂度 \(O(n\log n)\),足以通过本题
Code
#include <cstdio>
#include <iostream>
#include <algorithm>using namespace std;const int N = 1e5+10;int n;
int h[N] , g[N] , f[N] , dp[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);while(cin >> h[++ n]); n --;int len = 0;for(int i = 1 ; i <= n ; i ++) {dp[i] = 1;int l = 1 , r = len , res = 0 , mid;while(l <= r) {mid = (l+r) >> 1;if(f[mid] >= h[i]) {l = mid+1;res = mid;} else {r = mid-1;}}dp[i] = max(dp[i] , res+1);f[dp[i]] = max(f[dp[i]] , h[i]);len = max(len , dp[i]);}cout << len << '\n';len = 0;for(int i = 1 ; i <= n ; i ++) {int l = 1 , r = len , res = 0 , mid;while(l <= r) {mid = (l+r) >> 1;if(g[mid] >= h[i]) {r = mid-1;res = mid;} else {l = mid+1;}}if(!res) g[++ len] = h[i];else g[res] = h[i];}cout << len << '\n';return 0;
}