计蒜客：2019 蓝桥杯省赛 B 组模拟赛（一）代码填空：LIS

待我称王封你为后i 2022-02-27 23:38 180阅读 0赞

#                                          代码填空：LIS #

### 题目链接： ###

[https://nanti.jisuanke.com/t/A2237][https_nanti.jisuanke.com_t_A2237]

LIS 是最长上升子序列。什么是最长上升子序列？ 就是给你一个序列，请你在其中求出一段最长严格上升的部分，它不一定要连续。

就像这样：222, 333, 444, 777 和 222, 333, 444, 666 就是序列 222 555 333 444 111 777 666 的两个上升子序列，最长的长度是 444。

### 样例输入 ###

无

### 样例输出 ###

无

### 程序代码： ###

#include <bits/stdc++.h>
    using namespace std;
    const int N = 1e5 + 9;
    int f[N], a[N];
    int n;
    int find(int l, int r, int x) {
    	while (l < r) {
    		int mid = (l + r) / 2;
    		if (f[mid] < x) {
    			l = mid + 1;
    		} else {
    			r = mid;
    		}
    	}
    	return l;
    }
    int lis() {
    	int len = 0;
    	for (int i = 0; i < n; i++) {
    		int k=find(0,len,a[i]);    //填空 
    		f[k] = a[i];
    		if (k == len) {
    			len++;
    		}
    	}
    	return len;
    }
    int main() {
    	scanf("%d", &n);
    	for (int i = 0; i < n; i++) {
    		scanf("%d", a + i);
    	}
    	printf("%d\n", lis());
    	return 0;
    }

[https_nanti.jisuanke.com_t_A2237]: https://nanti.jisuanke.com/t/A2237

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯 2022 省赛 C++ B组

填空问题 [九进制转十进制][Link 1] > 九进制正整数 (2022)9 转换成十进制等于多少？ import java.util.Scanner;

阳光穿透心脏的1/2处/ 2024年03月24日 08:29/ 0 赞/ 85 阅读

相关【题解】计蒜客 2020 蓝桥杯大学 B 组省赛模拟赛（一）

试题目录 A. 结果填空：有趣的数字（签到） B. 结果填空：爬楼梯（dp） C. 结果填空：七巧板（数论） D. 结果填空：苹果（贪心）

落日映苍穹つ/ 2023年07月01日 03:24/ 0 赞/ 9 阅读

相关 2020蓝桥杯省赛模拟赛

目录第一题：第二题：第三题：第四题：第五题：第六题：第七题：第八题：第九题：第十题：

电玩女神/ 2022年12月13日 11:27/ 0 赞/ 204 阅读

相关计蒜客蓝桥杯模拟赛5 引爆炸弹

题目：在一个 n×m 的方格地图上，某些方格上放置着炸弹。手动引爆一个炸弹以后，炸弹会把炸弹所在的行和列上的所有炸弹引爆，被引爆的炸弹又能引爆其他炸弹，这样连锁下去。 !

以你之姓@/ 2022年06月15日 05:54/ 0 赞/ 172 阅读

相关蓝桥杯模拟赛B组

![SouthEast][] ![SouthEast 1][] 推理过程：由题意可知：2\A1=A0+A2-2\C1;(A2 = 2 \ A1 - A0 -> A2里

爱被打了一巴掌/ 2022年06月01日 05:41/ 0 赞/ 282 阅读

相关 2015蓝桥杯省赛B组----交换啤酒瓶

交换瓶子有N个瓶子，编号 1 ~ N，放在架子上。比如有5个瓶子： 2 1 3 5 4 要求每次拿起2个瓶子，交换它们的位置。经过若干次后，使得瓶子的序

左手的ㄟ右手/ 2022年05月28日 05:44/ 0 赞/ 335 阅读

相关 2019 蓝桥杯省赛 B 组模拟赛（一）代码填空：LIS (LIS二分写法)

LIS 是最长上升子序列。什么是最长上升子序列？就是给你一个序列，请你在其中求出一段最长严格上升的部分，它不一定要连续。就像这样：22, 33, 44, 77 和 22,

今天药忘吃喽~/ 2022年03月21日 09:24/ 0 赞/ 214 阅读

相关计蒜客：2019 蓝桥杯省赛 B 组模拟赛（一）程序设计：轻重搭配（贪心）

程序设计：轻重搭配 n 个同学去动物园参观，原本每人都需要买一张门票，但售票处推出了一个优惠活动，一个体重

桃扇骨/ 2022年02月28日 00:04/ 0 赞/ 203 阅读

相关计蒜客：2019 蓝桥杯省赛 B 组模拟赛（一）程序设计：后缀字符串（字典树）

程序设计：后缀字符串题目链接： [https://nanti.jisuanke.com/t/A22

男娘i/ 2022年02月27日 23:38/ 0 赞/ 169 阅读

相关计蒜客：2019 蓝桥杯省赛 B 组模拟赛（一）代码填空：LIS

代码填空：LIS 题目链接： [https://nanti.jisuanke.co

待我称王封你为后i/ 2022年02月27日 23:38/ 0 赞/ 181 阅读