「网络流 24 题6」最长递增子序列

题目描述:

给定正整数序列 x1∼xn​​，以下递增子序列均为非严格递增。

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

输入格式:

第 1 行有 1 个正整数 n ，表示给定序列的长度。接下来的 1 行有 n 个正整数 x1∼xn。

输出格式:

第 1 行是最长递增子序列的长度 s 。第 2 行是可取出的长度为 s 的递增子序列个数。第 3 行是允许在取出的序列中多次使用 x1  和 xn 时可取出的长度为 s 的递增子序列个数。

样例输入:

4
3 6 2 5

样例输出:

2
2
3

提示:

1≤n≤500

时间限制: 1000ms
空间限制: 256MB

---