当前位置: 首页 > news >正文

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

题目大意

共有两问

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

Sol

原数据是 \(1e4\) 的,所以先考虑 \(O(n^2)\) 做法。

  1. 第一问
    容易发现,这跟我们求最长不降子序列是一样的
    所以我们直接设状态为 \(dp_i\) 表示前 \(i\) 个数中所能得到的最长不升子序列长度
    转移如下:

\[dp_i= \left\{ \begin{array}{l}1 \\dp_j+1 & j<i\ 且\ h_j\geq h_i\end{array}\right. \]

  1. 第二问
    我们可以直接维护一个数组 \(g\) 表示到第 \(i\) 个最少需要的几个拦截装置的目前高度
    每次扫一遍 \(g\) 找到最小的 \(g_j\geq h_i\)\(g_j\) 更新为 \(h_i\)

总体空间复杂度 \(O(n)\),时间复杂度 \(O(n^2)\)


这样可以在原数据拿到 \(100\) 分,但为了拿到 \(200\) 分我们考虑一下 \(O(n\log n)\) 做法。

  1. 第一问
    我们主要的复杂度瓶颈在于找到最大的 \(dp_j\),所以考虑从这方面优化。
    容易发现,对于不同的长度,长度越长的最后的数字一定越小(短的在拼上一个小的就会变成长的)
    所以当长度递增时,每个长度结尾数的最大值一定单调不增,就满足了二分性质。
    再开一个数组 \(f_i\) 表示当长度为 \(i\) 是所能取得的最大结尾数字,在状态转移时二分一个最小的 \(f_j\geq h_i\)
    这时的答案就是 \(i+1\)
  2. 第二问
    有一个比较特殊的性质:如果按照上面的方式更新 \(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;
}
http://www.hskmm.com/?act=detail&tid=25312

相关文章:

  • RabbitMQ 离线安装
  • Nginx 离线安装
  • docker 离线安装
  • uniapp 转回tabbar页面
  • 第十一届中国大学生程序设计竞赛网络预选赛 魔塔
  • JDK 离线安装
  • minio 离线安装
  • HbuilderX 将 h5转成uniapp的一些记录.19127294
  • 银行同业存单产品的筛选方法
  • deepseek 私有部署文档
  • MySQL运维及开发规范
  • 短视频平台差异视角下开源AI智能名片链动2+1模式S2B2C商城小代码的适配性研究——以抖音与快手为例
  • 异步读写mysql依赖pymysql (asyncio/ aiomysql)
  • Linux发行版切换技术全解析
  • 手把手教你用 Docker 部署 Redis
  • 悟空博弈单元(WBUC)与广域统一计算(WAUC)研究:价值共生的技术基石——声明Ai研究
  • 掌握形式验证工具,提升芯片验证效率
  • 长租公寓的生存越来越难了 - 智慧园区
  • Spring Boot中保存前端上传的图片 - 教程
  • P2724 [IOI 1998 / USACO3.1] 联系 Contact 做题笔记
  • 深入解析:Linux运维笔记:服务器感染 netools 病毒案例
  • 设计模式——命令设计模式(行为型) - 详解
  • 港专专利申请量被反超,背后是谁在“偷家”?
  • 版权诉讼下的MiniMax:AI独角兽的上市迷途
  • HTB Eureka靶机渗透实战 - Spring Boot堆转储与Bash算术注入漏洞利用
  • 手机照片太多了存哪里? - 实践
  • 时隔十六年的南京之旅
  • 高贵的北上广深,没有父母托举,90后很难成家
  • 使用AI图像服务规模化视觉内容生产
  • 实用指南:基于贝叶斯优化神经网络的光伏功率预测综述