1843: 最长递增子序列问题
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给定正整数序列x1 , , xn 。
（1）计算其最长递增子序列的长度s。
（2）计算从给定的序列中最多可取出多少个长度为s的递增子序列。
（3）如果允许在取出的序列中多次使用x1和xn，则从给定序列中最多可取出多少个长
度为s的递增子序列。
设计有效算法完成（1）（2）（3）提出的计算任务。
输入
第1 行有1个正整数n，表示给定序列的长度。接
下来的1 行有n个正整数x1 , , xn 。
下来的1 行有n个正整数x1 , , xn 。
输出
第1 行是最长
递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出
的序列中多次使用x1和xn时可取出的长度为s 的递增子序列个数。
递增子序列的长度s。第2行是可取出的长度为s 的递增子序列个数。第3行是允许在取出
的序列中多次使用x1和xn时可取出的长度为s 的递增子序列个数。
样例输入 复制
4
3 6 2 5样例输出 复制
2
2
3