P3928 SAC E#1 - 一道简单题 Sequence2

小强和阿米巴是好朋友。

小强喜欢数列。有一天，他心血来潮，写下了三个长度均为 $n$ 的数列。 阿米巴也很喜欢数列。但是他只喜欢其中一种，波动数列。 阿米巴把他的喜好告诉了小强。小强便打算找出这三个数列内的最长波动数列。 也就是说，如果我们将三个数列记做 $a_{n,1},a_{n,2},a_{n,3}$，他必须要构造一个二元组序列：$(p_i,q_i)$，使得对于任何 $i>1$ 有： - $p_i>p_{i-1}$。 - 若 $q_i=0$，$a_{p_i,q_i} \ge a_{p_{i-1},q_{i-1}}$。 - 若 $q_i=1$，$a_{p_i,q_i} \le a_{p_{i-1},q_{i-1}}$。 - 若 $q_i=2$，只要保持段内同向即可（就是对于连续的一段 $q_i=2$，要么都有 $a_{p_i,q_i} \ge a_{p_{i-1},q_{i-1}}$，要么都有 $a_{p_i,q_i} \le a_{p_{i-1},q_{i-1}}$。 小强希望这个二元组序列尽可能长。 提示：当 $q_i \not = q_{i-1}$ 时，数列的增减性由 $q_i$ 而非 $q_{i-1}$ 决定。 **清晰版题目描述** 小强拿到一个 $3 \times n$ 的数组，要在每一列选一个数（或者不选），满足以下条件： 1. 如果在第一行选，那它必须大于等于上一个数。 2. 如果在第二行选，那么必须小于等于上一个数。 3. 如果在第三行选，对于连续的一段在第三行选的数，必须满足方向相同（都小于等于上一个数或者都大于等于上一个数）。

输入包含 $4$ 行。 第一行一个数 $n$，表示数列长度。 第 $2,3,4$ 行，每行 $n$ 个整数，分别表示三个数列。

输出仅包含一个整数，即最长波动数列的长度。

对于 $20\%$ 的数据，$n \le 10$，$m \le 1000$。 对于 $60\%$ 的数据，$n \le 1000$，$m \le 1000$。 对于 $100\%$ 的数据，$n \le 10^5$，$m \le 10^9$。 其中 $m=\max\{|a_i|\}$。 样例解释： 取第三行 $1,2,3$（增），然后取第一行 $6$（增），然后取第三行 $5,4$（减），长度为 $6$。