LIS+变形

LIS模板
变形：因为多了0的设置，所以采用把队列中已有的元素加1的形式进行为0元素空位
HDU 5773 The All-purpose Zero

给你一个长度为10W的数组，每个数范围0-100W
其中的0可以变为INT范围的任意值
问最长上升子序列的长度。

#include<bits/stdc++.h>
using namespace std;
int a[100008];
int dp[100008];
const int inf = 0x3f3f3f3f;
int main()
{
    int T;
    cin>>T;
    int id = 0;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        dp[0] = -inf;
        dp[1] = a[1];
        int Front = 0;
        int len = 1;
        for(int i=2;i<=n;i++)
        {
            if(a[i]>dp[len])
            {
                dp[++len] = a[i];
            }
            else if(a[i]==0)
            {
                for(int j=len;j>=Front;j--)
                {
                    dp[j+1]  = dp[j]+1;
                }
                len++;
                Front++;
            }
            else
            {
                int p  =lower_bound(dp,dp+len,a[i])-dp;
                dp[p] = a[i];
            }

        }
        id++;

        cout<<"Case #"<<id<<": "<<len<<endl;
    }

    return 0;
}