同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1618_最长递增子序列

2022-5-16 18:17| 发布者: Hocassian| 查看: 47| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-8950447112799-Problem List-采集的数据-后羿采集器.html

Pro.ID

1618

Title

最长递增子序列

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1618

AC

Submit

Ratio

45.45%

时间&空间限制

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

描述

给定正整数序列 x₁∼ x_n ，以下递增子序列均为非严格递增。

计算其最长递增子序列的长度 s 。
计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。
如果允许在取出的序列中多次使用 x₁ 和 x_n ，则从给定序列中最多可取出多少个长度为 s 的递增子序列。

输入

第 1 行有 1 个正整数 n ( 1 ≤ n ≤ 500 )，表示给定序列的长度。接下来的 1 行有 n 个正整数 x₁ ∼ x_n 。

输出

Description

给定正整数序列 x₁∼ x_n ，以下递增子序列均为非严格递增。

计算其最长递增子序列的长度 s 。
计算从给定的序列中最多可取出多少个长度为 s 的递增子序列。
如果允许在取出的序列中多次使用 x₁ 和 x_n ，则从给定序列中最多可取出多少个长度为 s 的递增子序列。

Input

第 1 行有 1 个正整数 n ( 1 ≤ n ≤ 500 )，表示给定序列的长度。接下来的 1 行有 n 个正整数 x₁ ∼ x_n 。

Output

第 1 行是最长递增子序列的长度 s 。

第 2 行是可取出的长度为 s 的递增子序列个数。

第 3 行是允许在取出的序列中多次使用 x₁ 和 x_n 时可取出的长度为 s 的递增子序列个数。

Sample Input

4
3 6 2 5

Sample Output

2
2
3

Source

网络流 24 题

样例输入