P3298. 反单调性

ID: 2299
传统题
1000ms
256MiB
尝试: 1
已通过: 0
难度: 10
上传者:

Hydro
标签:

题目描述

我有一个长度为 n 的序列 Fred，其中每个元素都是 1 到 n 之间的整数，且所有元素互不相同。我想找到 Fred 的一个最长子序列 Mary，满足以下性质：

Mary0 > Mary1 < Mary2 > Mary3 < ...

输入格式

第一行包含一个整数 T（无前导零），表示测试用例的数量，T 最大为 50。接下来是 T 个测试用例。

每个测试用例占一行，格式如下：
n Fred0 Fred1 Fred2 ... Fredn-1

其中 n 和 Fred 中的每个元素都是无前导零的整数。行中无首尾空格，相邻整数用单个空格分隔。n 最大为 30000。

输出格式

对每个测试用例，输出一个整数并换行，即满足条件的最长子序列 Mary 的长度。

输入数据示例 1

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

输出数据示例 1

1  
2  
5  
3  

来源

Waterloo 本地竞赛，2007.7.14