1368: 「网络流 24 题」最长递增子序列
[Creator : ]
Description
给定正整数序列 $x_1 \sim x_n$,以下递增子序列均为非严格递增。
- 计算其最长递增子序列的长度 s。
- 计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。
- 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$,则从给定序列中最多可取出多少个长度为 s 的递增子序列。
Input
第 1 行有 1 个正整数 n,表示给定序列的长度。
接下来的 1 行有 n 个正整数 $x_1 \sim x_n$。
接下来的 1 行有 n 个正整数 $x_1 \sim x_n$。
Output
第 1 行是最长递增子序列的长度 s。
第 2 行是可取出的长度为 s 的递增子序列个数。
第 3 行是允许在取出的序列中多次使用 $x_1$ 和 $x_n$ 时可取出的长度为 s 的递增子序列个数。
第 2 行是可取出的长度为 s 的递增子序列个数。
第 3 行是允许在取出的序列中多次使用 $x_1$ 和 $x_n$ 时可取出的长度为 s 的递增子序列个数。
Constraints
$1 \leq n \leq 500$
Sample 1 Input
4
3 6 2 5
Sample 1 Output
2
2
3