📅 发布时间：2026/6/19 8:13:38

题目大意

共有两问

求最长不升子序列
求最少能分为几个不升子序列

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;
}

luogu P1020 [NOIP 1999 提高组] 导弹拦截

题目大意

Sol

Code