最长上升子序列 二分做法

2024-09-04 23:18

本文主要是介绍最长上升子序列 二分做法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定一个长度为N的数列,求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数N。

第二行包含N个整数,表示完整序列。

输出格式

输出一个整数,表示最大长度。

数据范围

1≤N≤10001≤N≤1000,
−109≤数列中的数≤109−109≤数列中的数≤109

输入样例:

7
3 1 2 1 8 5 6

输出样例:

4

二分做出的答案只有数量是最长上升子序列的长度,并没有保存他这个方案。 二分的做法就是通过二分查找维护一个单调递增的序列。 

首先创建一个存储最大上升子序列的数组q然后遍历要求的序列,如果说当前这个数比q的尾数还要大的话那么肯定就能构成一个更长的上升子序列,如果小的话那么就找出第一个大于他的数(前面也说了并没有保存他的方案只是找出数量)把他替换掉,如果还有比队尾大的数要入队的话改变前面的位置对后面是没有影响的,而如果有比队尾小的话向前找也可以做到让这个"新"数列尽可能地长(如果这个新的能覆盖原来的序列的话那么最长的就是这个新的,否则就还是原来的那个)这个就相当于在一个数组里存了好多有可能成为最长上升子序列的字串然后不断扩展他们的可能。很神奇

#include <iostream>
#include <cmath>
#include <string.h>
#include <algorithm>
#include <map>
#include <queue>
typedef  long long ll;
using namespace std;
int n,m;
int a[10010],dp[510][510];
vector<int>q;
int main()
{q.clear();int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];if(q.empty()||a[i]>q.back())q.push_back(a[i]);else{int l=0,r=q.size();while(l<r){int mid=l+r>>1;if(q[mid]>=a[i])r=mid;elsel=mid+1;}q[l]=a[i];}}cout<<q.size()<<endl;
}

 

这篇关于最长上升子序列 二分做法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1137312

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意: n件湿度为num的衣服,每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉,每秒可以烧掉k个湿度,但不计算蒸发了。 现在问这么多的衣服,怎么烧事件最短。 解析: 二分答案咯。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意: 有一些石头排成一条线,第一个和最后一个不能去掉。 其余的共可以去掉m块,要使去掉后石头间距的最小值最大。 解析: 二分石头,最小值最大。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2594 二分图最大独立集

题意: 求一张图的最大独立集,这题不同的地方在于,间接相邻的点也可以有一条边,所以用floyd来把间接相邻的边也连起来。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta

poj 3692 二分图最大独立集

题意: 幼儿园里,有G个女生和B个男生。 他们中间有女生和女生认识,男生男生认识,也有男生和女生认识的。 现在要选出一些人,使得这里面的人都认识,问最多能选多少人。 解析: 反过来建边,将不认识的男生和女生相连,然后求一个二分图的最大独立集就行了。 下图很直观: 点击打开链接 原图: 现图: 、 代码: #pragma comment(