Preparing NOJ

A. 智能飞弹

2000ms 65536K

Description:

    魁拔军团为抵御神界的攻击,在涡流岛上自顶向下建立了N道防御屏障,第i道屏障能量厚度为Di。神界势要灭掉魁拔,发明了一种能在行进路径上挑选可击破屏障进行击破的智能飞弹,这种飞弹的优点是可以击破并不连续存在的屏障,缺点是飞弹击破的下一道屏障的能量厚度必须严格小于当前击破的一道,且飞弹只能从上往下逐次击破而不能倒飞。比如有5道屏障,自上而下能量厚度分别为5,3,4,2,1,则一个可行的击破序列为5,4,2,1,并且这也是最长的一个可击破序列,另一个序列如5,3,4由于位于后方的屏障厚度为4大于其前方的屏障,所以是个不能击破的序列。
    现在给出魁拔的屏障设置,求最长可击破的序列长度。

Input:

    第一行包含一个正整数T(T≤100),表示样例个数,接下来给出T组测试用例。
    每组测试用例包含两行,第一行为一个正整数N(1≤N≤100000),表示有N道屏障,第二行有N个用空格隔开的正整数Di(1≤Di≤100000),表示自上而下各道屏障的能量厚度。

Output:

    每组测试用例输出一行结果,包含一个整数,表示最长可击破的序列长度。

Sample Input:

2
5
5 3 4 2 1
5
1 1 1 1 1

Sample Output:

4
1

Note:

 

本题由旧版NOJ导入,来源:ACM爱好者协会

Info

NOJ

Provider NOJ

Code NOJ1858

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet