The All-purpose Zero
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Submit
Status
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.
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.
题意
：
给你n个数，可以将其中的0变成任何数，问可以得到的最长的上升子序列；
思路：
因为0可以变成任何数，甚至是负数，
考虑到底以一个数的结尾的最长上升序列，加入前面0的个数多少来变化能使这个长度变为最长，因为要加入0来变化，所以一定可以改变0的大小来使这个序列递增，所以将出现的0全部用上是对的，然后对其他的数进行(n*logn)的LIS
但是插入0是有花费的，比如4 0 5；那么这个时候只能让当前的数减去前面0的个数，来抵消这个花费，因为每个0只消耗一点花费，所以将前面所有0加入，可保证到这个
数的序列最长。然后先将非0的求LIS。
代码：
<pre name="code" class="cpp">#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define INF (1<<31-1)
int a[100010];
int dp[100010];
int main()
{int t,n,mm=1;scanf("%d",&t);while(t--){int cnt=0,t=0;scanf("%d",&n);while(n--){int b;scanf("%d",&b);if(b==0)cnt++;elsea[++t]=b-cnt; }for(int i=0;i<=t;i++){dp[i]=INF;}for(int i=1;i<=t;i++){*lower_bound(dp,dp+t,a[i])=a[i];}printf("Case #%d: %d\n",mm++,lower_bound(dp,dp+t,INF)-dp+cnt);}return 0;
}