题目背景
翻译自 ROI 2023 D1T3。
如果对于所有 1≤j<i,都有 aj<ai,则称 ai 为峰值。
如果对于所有 1≤j<i,都有 aj>ai,则称 ai 为反峰值。
题目描述
给定大小为 n 的排列 p1,p2,…,pn。需要将其分为两个非空子序列 q 和 r。每个元素 p 必须恰好被分到一个子序列中。你需要最大化 q 中的峰值数量和 r 中的反峰值数量之和。
输入格式
每个测试点由多组数据组成。第一行包含一个整数 t(1≤t≤100,000),表示数据组数。接下来的 2t 行,每两行是一组数据。
每组数据的第一行包含一个整数 n(2≤n≤200,000),表示排列的大小。
每个输入数据集的第二行包含 n 个整数 p1,p2,…,pn,表示原始排列。保证 p 中的每个数字都恰好出现一次。
每组数据中 n 的总和不超过 200,000。
输出格式
对于每组数据,输出一个整数,表示将 p 拆分后,q 中的峰值数量和 r 中的反峰值数量之和的最大值。
4
5
4 1 2 3 5
10
3 8 10 4 1 2 7 9 5 6
3
1 2 3
6
4 2 5 1 6 3
5
6
3
5
提示
前两个样例解释:
设 N=∑n。
Subtask |
分值 |
n,N |
特殊性质 |
1 |
21 |
n≤16 |
t≤120 |
2 |
22 |
n≤200,N≤2000 |
|
3 |
14 |
N≤2000 |
4 |
10 |
N≤20000 |
5 |
13 |
N≤200000 |
p 的最大递减子序列的长度不超过 2 |
6 |
20 |
|