POJ 1631 Bridging signals 最长上升子序列小结 LIS的O(nlogn)算法

2023-10-17 09:38

本文主要是介绍POJ 1631 Bridging signals 最长上升子序列小结 LIS的O(nlogn)算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

POJ 1631 Bridging signals

题目分析:
题目要求避免相交,则可转化为对给定的序列求最长上升子序列。

首先使用了dp来求解,复杂度为O(n*n),在题目的数据范围下超时了…

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[40000];
int num[40000];
int main() {int t;scanf("%d", &t);while (t--) {int p;scanf("%d", &p);for (int i = 1; i <= p; i++) {scanf("%d", &num[i]);dp[i] = 1;}for (int i = 1; i <= p; i++) {for (int j = 1; j < i; j++) {if (num[j] < num[i]) {dp[i] = max(dp[i], dp[j] + 1);}}}int ans = 0;for (int i = 1; i <= p; i++) {//cout << "dp " << dp[i] << endl;ans = max(ans, dp[i]);}//cout << "ans " << ans << endl;cout << ans << endl;}//system("pause");
}

于是参考各类大神们的博客,学习了LIS问题的O(nlogn)算法

LIS问题的O(nlogn)算法

定义ans[k] : 长度为k的上升子序列的最末尾元素,若有多个长度为k的上升子序列,则保存值最小的末尾元素
定义len用于保存ans数组的长度,也即目前能够得到的最长子序列长度
定义num[]数组来保存给定的序列

易得初始化条件为:ans[1]=num[1], len=1
下面对其余的序列元素进行遍历:

for (int i = 2; i <= n; i++) {新的元素大于目前最长子序列的末尾元素,则添加到序列尾部if (num[i] > ans[len]) {ans[++len] = num[i];}/*否则找到新的元素num[i]所能构成的最长子序列长度,此时num[i]小于原先时候该长度的末尾元素,用num[i]替换原末尾元素*/else {int tmp = binary_search(i);//在ans序列中返回大于num[i]的最小下标ans[tmp] = num[i];}
}

这里有ans[tmp-1]<num[i]<ans[tmp]
注意ans数组是单调的(递增),在ans中插入新元素时无需挪动(操作为在尾部添加或者替换前面的元素)——也就是说我们可以使用二分查找,将每一个数字num[i]的插入时间优化到O(logn)~~~~~于是算法总的时间复杂度就降低到了O(nlogn)~!
即利用ans数组的单调性,在查找tmp的时候可以二分查找,从而总的时间复杂度为nlogn

AC代码

/*二分搜索-----最长上升子序列nlogn算法
*/
#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;
int num[40001], ans[40001], len;int binary_search(int i) {//在ans序列中返回大于num[i]的最小下标int left, right, mid;left = 1, right = len;while (left < right) {mid = left + (right - left) / 2;if (ans[mid] > num[i])right = mid;else left = mid + 1;}return left;
}
int main() {int t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &num[i]);}ans[1] = num[1]; len = 1;for (int i = 2; i <= n; i++) {if (num[i] > ans[len]) {ans[++len] = num[i];}else {int tmp = binary_search(i);//使用stl中的lower_bound函数//int tmp = lower_bound(ans + 1, ans + 1 + len, num[i]) -ans; ans[tmp] = num[i];}}cout << len << endl;}
}

注意ans数组形成的序列并不是最长的递增子序列!!!请看上面的ans数组定义!!!

下面是一个简易的示例:

		num 4  2  6  3  1  5
初始化	ans 4
i=2		.   2
i=3		.	2  6
i=4		.	2  3
i=5		.	1  3
i=6		. 	1  3  5
最终结果len=3,即最长的递增子序列长度为3
但1 3 5显然无法从给定序列中构成
ans[1]=1意味着长度为1的递增子序列末尾长度最小为1
ans[2]=3意味着长度为2的递增子序列末尾长度最小为3
ans[3]=5意味着长度为3的递增子序列末尾长度最小为5

这篇关于POJ 1631 Bridging signals 最长上升子序列小结 LIS的O(nlogn)算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/224517

相关文章

C#中Guid类使用小结

《C#中Guid类使用小结》本文主要介绍了C#中Guid类用于生成和操作128位的唯一标识符,用于数据库主键及分布式系统,支持通过NewGuid、Parse等方法生成,感兴趣的可以了解一下... 目录前言一、什么是 Guid二、生成 Guid1. 使用 Guid.NewGuid() 方法2. 从字符串创建

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Redis分片集群、数据读写规则问题小结

《Redis分片集群、数据读写规则问题小结》本文介绍了Redis分片集群的原理,通过数据分片和哈希槽机制解决单机内存限制与写瓶颈问题,实现分布式存储和高并发处理,但存在通信开销大、维护复杂及对事务支持... 目录一、分片集群解android决的问题二、分片集群图解 分片集群特征如何解决的上述问题?(与哨兵模

SpringBoot中使用Flux实现流式返回的方法小结

《SpringBoot中使用Flux实现流式返回的方法小结》文章介绍流式返回(StreamingResponse)在SpringBoot中通过Flux实现,优势包括提升用户体验、降低内存消耗、支持长连... 目录背景流式返回的核心概念与优势1. 提升用户体验2. 降低内存消耗3. 支持长连接与实时通信在Sp

Python打印对象所有属性和值的方法小结

《Python打印对象所有属性和值的方法小结》在Python开发过程中,调试代码时经常需要查看对象的当前状态,也就是对象的所有属性和对应的值,然而,Python并没有像PHP的print_r那样直接提... 目录python中打印对象所有属性和值的方法实现步骤1. 使用vars()和pprint()2. 使

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API,结合WebAudioAPI,实现网页录音功能,从获取音频流到处理和保存录音,整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3

Java对异常的认识与异常的处理小结

《Java对异常的认识与异常的处理小结》Java程序在运行时可能出现的错误或非正常情况称为异常,下面给大家介绍Java对异常的认识与异常的处理,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参... 目录一、认识异常与异常类型。二、异常的处理三、总结 一、认识异常与异常类型。(1)简单定义-什么是

Python函数返回多个值的多种方法小结

《Python函数返回多个值的多种方法小结》在Python中,函数通常用于封装一段代码,使其可以重复调用,有时,我们希望一个函数能够返回多个值,Python提供了几种不同的方法来实现这一点,需要的朋友... 目录一、使用元组(Tuple):二、使用列表(list)三、使用字典(Dictionary)四、 使

Python程序的文件头部声明小结

《Python程序的文件头部声明小结》在Python文件的顶部声明编码通常是必须的,尤其是在处理非ASCII字符时,下面就来介绍一下两种头部文件声明,具有一定的参考价值,感兴趣的可以了解一下... 目录一、# coding=utf-8二、#!/usr/bin/env python三、运行Python程序四、

Python中合并列表(list)的六种方法小结

《Python中合并列表(list)的六种方法小结》本文主要介绍了Python中合并列表(list)的六种方法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋... 目录一、直接用 + 合并列表二、用 extend() js方法三、用 zip() 函数交叉合并四、用