#760. #6005. 「网络流 24 题」最长递增子序列

#6005. 「网络流 24 题」最长递增子序列

题目描述

给定正整数序列 x1∼xnx_1 \sim x_n,以下递增子序列均为非严格递增。

  1. 计算其最长递增子序列的长度 ss。
  2. 计算从给定的序列中最多可取出多少个长度为 ss 的递增子序列。
  3. 如果允许在取出的序列中多次使用 x1x_1 和 xnx_n,则从给定序列中最多可取出多少个长度为 ss 的递增子序列。

输入格式

文件第 11 行有 11 个正整数 nn,表示给定序列的长度。接下来的 11 行有 nn 个正整数 x1∼xnx_1 \sim x_n。

输出格式

第 11 行是最长递增子序列的长度 ss。第 22 行是可取出的长度为 ss 的递增子序列个数。第 33 行是允许在取出的序列中多次使用 x1x_1 和 xnx_n 时可取出的长度为 ss 的递增子序列个数。

4
3 6 2 5
2
2
3

数据范围与提示

1≤n≤5001 \leq n \leq 500