题目 30182

最长上升子序列

查看题解 ↗GitHub ↗如何评测
题号
30182
时间限制
10000 ms
内存限制
1024 MB
标签
动态规划贪心
来源
Library Checker (yosupo06) - longest_increasing_subsequence

【题目描述】

给定一个长度为 NN 的整数序列 AA。请找出 AA 的一个最长上升子序列。

【输入】

文本
$N$
$A_0$ $A_1$ $\dots$ $A_{N - 1}$

【输出】

第 1 行输出上升子序列的最大长度 KK。 第 2 行输出一个长度为 KK 的上升子序列。 iki_k 是该子序列的第 kk 个元素的下标。

文本
$K$
$i_0$ $i_1$ $\dots$ $i_{K - 1}$

【输入样例】

文本
5
3 1 4 1 5

【输出样例】

文本
3
1 2 4

【输入样例2】

文本
5
3 3 2 3 1

【输出样例2】

文本
2
2 3

【数据范围】

  • 1≤N≤5000001 \leq N \leq 500000
  • 0≤Ai≤10000000000 \leq A_i \leq 1000000000

【来源】

Library Checker(yosupo06) longest_increasing_subsequence

本题为 special judge(输出任意合法解),暂不可本地评测。

数据下载

题目 30182 的公开数据

正在读取文件列表…

常用命令

题目 30182 的 ROJ 命令

以下命令默认使用全局安装的 ROJ Skill,请在终端中直接执行;如果修改过 AGENT_HOME,请将命令中的 ~/.agents 替换为对应目录。