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

2097_最长递增子序列

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

摘要:

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

Pro.ID

2097

Title

最长递增子序列

Title链接

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

AC

Submit

Ratio

0.00%

时间&空间限制

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

描述

给定正整数序列x₁ , ..., x_n 。

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

设计有效算法完成 1. 2. 3.提出的计算任务。

输入

输入的第一行有1个正整数n，表示给定序列的长度。接下来的一行有n个正整数 x₁ , ... , x_n 。

输出

Description

给定正整数序列x₁ , ..., x_n 。

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

设计有效算法完成 1. 2. 3.提出的计算任务。

Input

输入的第一行有1个正整数n，表示给定序列的长度。接下来的一行有n个正整数 x₁ , ... , x_n 。

Output

输出任务 1. 2. 3.的解答。

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

Sample Input

4
3 6 2 5

Sample Output

2
2
3

Author

John

样例输入