hdu 5773 The All-purpose Zero(贪心+最长上升子序列)

Problem Description
?? gets an sequence S with n intergers(0 < n <= 100000,0<= S[i] <= 1000000).?? has a magic so that he can change 0 to any interger(He does not need to change all 0 to the same interger).?? wants you to help him to find out the length of the longest increasing (strictly) subsequence he can get.

 

Input
The first line contains an interger T,denoting the number of the test cases.(T <= 10) For each case,the first line contains an interger n,which is the length of the array s. The next line contains n intergers separated by a single space, denote each number in S.

 

Output
For each test case, output one line containing “Case #x: y”(without quotes), where x is the test case number(starting from 1) and y is the length of the longest increasing subsequence he can get.

 

Sample Input
2
7
2 0 2 1 2 0 5
6
1 2 3 3 0 0

 

Sample Output
Case #1: 5
Case #2: 5

Hint

In the first case,you can change the second 0 to 3.So the longest increasing subsequence is 0 1 2 3 5

看了一下数据范围肯定要nlogn计算LIS了,赶快去复习了一下加强了一下理解,其实感觉nlogn的算法也是一种贪心,保证了相同长度下结尾元素尽可能的小,可以使LIS的结果不会更差。
这道题目说0是可以变成任意数字的,那么肯定是要全部使用0的,这样并不会使结果变得更差,所以我们可以最后的答案是0的数字+nlgon求出的LIS长度。
但是这样就有一个问题,假如0被包括在了LIS序列内怎么办?赶快去请教了一下李大爷,被教育了:每个数原来的值减去他之前0的个数再做LIS就可以了。比如如果1前面有2个0就变成-1之类的。这样做的理由是,我们考虑0在加入LIS中肯定是要变成某些数字来保证严格递增的,假设最后得到的序列是这样的:1,0,3,0,0,9(这里非0数字并未减去他之前的0的数目)那么两个之前不是0的数字a,b之间的那些0要保证递增,那么相互之间差1才是最起码的条件。那么这两个数字之间abs(a-b)一定要满足这个条件。所以这么做,有点神啊这个思路。

发表评论

电子邮件地址不会被公开。 必填项已用*标注