F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Removed Interval

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2841    Accepted Submission(s): 881


Problem Description
Given a sequence of numbers $A=a_1,a_2,¡­,a_N$, a subsequence $b_1,b_2,¡­,b_k$ of $A$ is referred as increasing if $b_1<b_2<¡­<b_k$. LY has just learned how to find the longest increasing subsequence (LIS).
Now that he has to select $L$ consecutive numbers and remove them from $A$ for some mysterious reasons. He can choose arbitrary starting position of the selected interval so that the length of the LIS of the remaining numbers is maximized. Can you help him with this problem?
 

Input
The first line of input contains a number $T$ indicating the number of test cases ($T¡Ü100$).
For each test case, the first line consists of two numbers $N$ and $L$ as described above ($1¡ÜN¡Ü100000,0¡ÜL¡ÜN$). The second line consists of $N$ integers indicating the sequence. The absolute value of the numbers is no greater than $10^9$.
The sum of N over all test cases will not exceed 500000.
 

Output
For each test case, output a single line consisting of ¡°Case #X: Y¡±. $X$ is the test case number starting from 1. $Y$ is the maximum length of LIS after removing the interval.
 

Sample Input
2 5 2 1 2 3 4 5 5 3 5 4 3 2 1
 

Sample Output
Case #1: 3 Case #2: 1
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-12-11 21:52:32, Gzip enabled