利用O（nlogn）的LIS的思路题

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5773

题意：T组数据，每组数据是长度为n的数组，其中0可以换为任意的整数（可以使复数）问这个数组的最长上升子序列（严格上升）

思路：我们发现在选择的子序列左侧和右侧的每个0都能使得整个数组的长度增加1，但如果零实在选择的序列的中间时则取决于两个数字的value差与零的个数如1 2 0 0 3,1 2 0 0 3 4 5 6.我们发现无论什么情况算零都是合理的，把零算在最长子序列中会影响原来得到的序列。

那么题解来了，只要统计每个位置的数字之前零的个数，将该数字减去零的个数。然后用nlogn的算法求最长上升子序列，最后再加上所有零的个数

减去零的个数的意思就是把其前面所有的零算上得到的结果

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
using namespace std;
int a[100005];
bool idx[100005];
int lis[100005];
int main()
{
    //freopen("in.txt","r",stdin);
    int T,n;
    scanf("%d",&T);
    for(int t = 1; t <= T; t ++)
    {
        memset(idx,false,sizeof(idx));
        int znum = 0;
        scanf("%d",&n);
        for(int i = 0; i < n; i ++)
        {
            scanf("%d",&a[i]);
            if(a[i] == 0)
            {
                znum ++;
                idx[i] = true;
            }
            a[i] -= znum;
        }
        int p;
        int len = 0;
        for(int i = 0; i < n; i ++)
        {
            if(idx[i] == true)
                continue;

            p = lower_bound(lis,lis +len,a[i]) - lis;
            lis[p] = a[i];
            if(p == len)
                len ++;
        }
        printf("Case #%d: %d\n",t,len + znum);

    }

    return 0;
}