利用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;
}