【模板】O(nlongn)求LIS
2024-09-08 12:27:57
合理运用单调性降低复杂度
平常用的都是O(n^2)的dp求LIS(最长不下降子序列)
这里介绍O(nlogn)的算法
分析
- 对于可能出现的
x<y<i
且A[y]<A[x]<A[i]
,则x相对于y更有潜力- 因为接下来可能出现
A[y]<A[z]<A[x]
而x<z<i
;
- 因为接下来可能出现
- 我们以
f[i]
表示前i
个数中的LIS最长长度;- 当出现
f[x]==f[y]
时,就应该选择x
而不会是y
- 当出现
- 我们可以得到以下思想
- 首先根据
f[]
值分类,记录满足f[t]=k
的最小的值a[t]
,记d[k]=min{a[t]},f[t]=k
. - 1.发现
d[k]
在计算过程中单调不上升 - 2.
d[1]<d[2]<...<d[k]
(反证) 1 2 3 8 4 7
- 首先根据
- 由此得到解法
- 设当前最长递增子序列为len,考虑元素a[i];
- 若
d[len]<a[i]
,则len++
,并将d[len]=a[i]
;否则,在d[0-len]
中二分查找,找到第一个比它小的元素d[k]
,并令d[k+1]=a[i]
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 41000;
int a[N]; //a[i] 原始数据
int d[N]; //d[i] 长度为i的递增子序列的最小值
int BinSearch(int key, int* d, int low, int high) {
while(low<=high) {
int mid = (low+high)>>1;
if(key>d[mid] && key<=d[mid+1])
return mid;
else if(key>d[mid]) low=mid+1;
else high=mid-1;
}
return 0;
}
int LIS(int* a, int n, int* d) {
int i,j;
d[1]=a[1];
int len=1; //递增子序列长度
for(i=2; i<=n; i++) {
if(d[len]<a[i]) j=++len;
else j=BinSearch(a[i],d,1,len)+1;
d[j]=a[i];
}
return len;
}
int main() {
int t;
int p;
scanf("%d",&t);
while(t--)
{
scanf("%d",&p);
for(int i = 1; i <= p; i++) scanf("%d",&a[i]);
printf("%d\n",LIS(a,p,d));
}
return 0;
}
最新文章
- javascript代码 调试方法
- mac上启动和停止mysql
- 转载-centos网络配置(手动设置,自动获取)的2种方法
- 在MyEclipse下创建Java Web项目 入门(图文并茂)经典教程
- maven打包异常:软件包com.sun.org.apache.xml.internal.security.utils.Base64 不存在
- MSP430常见问题之指令系统类
- 图论(无向图的割顶):POJ 1144 Network
- 制作openstack用的centos6.5镜像
- 完整具体解释GCD系列(二)dispatch_after;dispatch_apply;dispatch_once
- emqtt 试用(八)ssl认证 - 代码验证
- 【java】-- 线程安全
- DW1000 用户手册中文版 附录2 IEEE-802.15.4 MAC层
- struts转发和重定向action
- Chrome实用技巧集锦
- ELK 的插件安装(head)
- 老树开新花:DLL劫持漏洞新玩法
- springweb flux websocket
- POJ 3171 DP
- 【C++】指针的引用及面向对象
- 搞懂分布式技术2:分布式一致性协议与Paxos,Raft算法
热门文章
- js--吐血总结最近遇到的变态表单校验---element+原生+jq+easyUI(前端职业生涯见过的最烦的校验)
- 【odoo】[经验分享]数据迁移注意事项
- 使用FastDFS进行文件管理
- 使用find_if算法搜寻map的value
- Java开发人员最容易出现的几类错误
- [并发编程 - 多线程:信号量、死锁与递归锁、时间Event、定时器Timer、线程队列、GIL锁]
- golang:协程安全
- kenel 和shell
- BUUCTF(九) [ACTF2020 新生赛]Exec 1
- openstack总结复习