当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

5141:LIS again

题目描述
A numeric sequence of ai is ordered if $a_1 < a_2 < \ldots < a_N$. Let the subsequence of the given numeric sequence ($a_1, a_2, \ldots , a_N$) be any sequence ($a_{i_1}, a_{i_2}, \ldots , a_{i_K}$), where $1 \leq i_1 < i_2 < \ldots < i_K \leq N$. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, eg. (1, 7), (3, 4, 8) and many others.
S[ i , j ] indicates ( $a_i, a_{i+1}, a_{i+2}, \ldots, a_j$) .
Your program, when given the numeric sequence ($a_1, a_2, \ldots , a_N$), must find the number of pair ( i, j) which makes the length of the longest ordered subsequence of S[ i , j ] equals to the length of the longest ordered subsequence of ($a_1, a_2, \ldots , a_N$).
输入解释
Multi test cases (about 100), every case occupies two lines, the first line contain n, then second line contain n numbers $a_1, a_2, \ldots , a_N$ separated by exact one space.
Process to the end of file.

[Technical Specification]
$1 \leq n \leq 100000$
$0 \leq a_i \leq 1000000000$
输出解释
For each case,.output the answer in a single line.
输入样例
3
1 2 3
2
2 1
输出样例
1
3
来自杭电HDUOJ的附加信息
Recommend heyang

该题目是Virtual Judge题目,来自 杭电HDUOJ

题目来源 BestCoder Round #21

源链接: HDU-5141

最后修改于 2020-10-25T23:20:09+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 32768/32768K(Java/Others)