#P3927. [Neerc2014]Improvements

    ID: 3129 传统题 1000ms 128MiB 尝试: 30 已通过: 19 难度: 7 上传者: 标签>CF2300提高+/省选-最长上升子序列线性 DP树状数组前后缀状态分解

[Neerc2014]Improvements

题目描述

给出一个 11 到 NN 的全排列,要求选出一个尽可能长的子序列,满足:

  1. 不存在两个数 0≤i<j<N0\le i< j< N 满足线段 [min⁡(Ai,Ai+1),max⁡(Ai,Ai+1)][\min(A_i,A_{i+1}),\max(A_i,A_{i+1})] 和线段 [min⁡(Aj,Aj+1),max⁡(Aj,Aj+1)][\min(A_j,A_{j+1}),\max(A_j,A_{j+1})] 有交但不互相包含;
  2. A0A_0 一直为 00。

例如 (1,5,3,4)(1,5,3,4) 和 (1,5,3,2)(1,5,3,2) 是两个合法方案并且在后面加上任意一个数都将导致不合法。

(3,5,1)(3,5,1) 不合法是因为 [0,3][0,3] 和 [1,5][1,5] 相交但不互相包含。

输入格式

第一行包含一个整数 NN,意义见题目描述。

第二行包含 NN 个整数,表示给定的全排列。

输出格式

输出一个整数,表示子序列的最大长度。

4
1 3 2 4
3
4
1 4 2 3
4

样例说明

第一个样例把 33 去掉以后就合法了。

第二个样例没有冲突,直接输出 44。

数据规模与约定

对于 100%100\% 的数据,保证 1≤N≤2×1051\le N\le 2\times 10^5。

题目来源

ACM ICPC 2014-2015, NorthEastern European Regional Contest, Problem I