A2117 | $最长不下降子序列问题$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

给定正整数序列 $x_1 \ldots, x_n$。 1. 计算其最长不下降子序列的长度 $s$。 2. 如果每个元素只允许使用一次，计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。 3. 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$（其他元素仍然只允许使用一次），则从给定序列中最多可取出多少个**不同的**长度为 $s$ 的不下降子序列。 令 $a_1, a_2, \ldots, a_s$ 为构造 $S$ 时所使用的下标，$b_1, b_2, \ldots, b_s$ 为构造 $T$ 时所使用的下标。且 $\forall i \in [1,s-1]$，都有 $a_i \lt a_{i+1}$，$b_i \lt b_{i+1}$。则 $S$ 和 $T$ **不同**，当且仅当 $\exists i \in [1,s]$，使得 $a_i \neq b_i$。

第一行有一个正整数 $n$，表示给定序列的长度。接下来的一行有 $n$ 个正整数$x_1, ..., x_n$。

- 第 1 行是最长不下降子序列的长度 $s$。 - 第 2 行是可取出的长度为 $s$ 的不下降子序列个数。 - 第 3 行是允许在取出的序列中多次使用 $x_1$ 和 $x_n$ 时可取出的长度为 $s$ 的**不同的**不下降子序列个数。

输入 #1

4
3 6 2 5

输出 #1

2
2
3

C++ 编辑器

输入

输出