首页 > 编程语言 > 详细

18.10.9 不好做的最长上升子序列(nlogn树状数组解LIS)

时间:2018-10-09 23:51:33      阅读:412      评论:0      收藏:0      [点我收藏+]

描述

一个数的序列bi,当b1 < b2 < ... < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1a2, ..., aN),我们可以得到一些上升的子序列(ai1ai2, ..., aiK),这里1 <= i1 < i2 < ... < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8).

你的任务,就是对于给定的序列,求出最长上升子序列的长度。

输入

输入的第一行是序列的长度N (1 <= N <= 300000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到100000000之间。输出最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

4
技术分享图片
 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <stack>
 5 #include <string>
 6 #include <math.h>
 7 #include <queue>
 8 #include <stdio.h>
 9 #include <string.h>
10 #include <vector>
11 
12 #define lowbit(x) x&(-x)
13 
14 using namespace std;
15 
16 struct node {
17     int pos,value;
18     bool operator<(node a) {
19         if (value == a.value)
20             return pos > a.pos;
21         return value < a.value;
22     }
23 };
24 
25 const int maxn = 300005;
26 node n[maxn];
27 int N,c[maxn];
28 
29 int query(int pos) {
30     int res = 0;
31     while (pos > 0) {
32         res = max(c[pos], res);
33         pos -= lowbit(pos);
34     }
35     return res;
36 }
37 
38 void change(int pos,int len) {
39     while (pos <= N) {
40         c[pos] = max(c[pos], len);
41         pos += lowbit(pos);
42     }
43 }
44 
45 int getmax() {
46     int s = N,res=0;
47     while (s > 0) {
48         res = max(res, c[s]);
49         s -= lowbit(s);
50     }
51     return res;
52 }
53 
54 void process() {
55     for (int i = 1; i <= N; i++) {
56         int lis;
57         lis = query(n[i].pos) + 1;
58         change(n[i].pos, lis);
59     }
60     printf("%d\n", getmax());
61 }
62 
63 
64 int main()
65 {
66     scanf("%d", &N);
67     for (int i = 1; i <= N; i++) {
68         int val;
69         scanf("%d", &val);
70         n[i].pos = i, n[i].value = val;
71     }
72     sort(n + 1, n+N+1);
73     process();
74     return 0;
75 }
View Code

我很好奇他们是怎么发现数据的范围一开始是错的??

课上睡着了没听到这题,看了PPT做的

18.10.9 不好做的最长上升子序列(nlogn树状数组解LIS)

原文:https://www.cnblogs.com/yalphait/p/9763714.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!