Preparing NOJ

最长递增子序列问题

1000ms 65536K

Description:

 

 给定正整数序列x1 , …, x n

1)计算其最长递增子序列的长度s

2)计算从给定的序列中最多可取出多少个长度为s的递增子序列。

3)如果允许在取出的序列中多次使用x1x n,则从给定序列中最多可取出多少个长度为s的递增子序列。

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

Input:

       第1行有1个正整数n,表示给定序列的长度。接下来的1行有n个正整数  x1 , …, x n

Output:

 

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

Sample Input:

4
3 6 2 5

Sample Output:

2
2
3

Note:

 

本题由旧版NOJ导入,来源: 算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1353

Tags

Submitted 1

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet