#P2088. 上升序列

#P2088. 上升序列

题目描述

给一个长度 /(10^5/) 的非负序列，序列中的0可以任意换成任何数字（包括负数），问最长严格上升子序列长度。

输入格式

第一行有一个数 /(n/) 代表序列长度

第二行有 /(n/) 个数字 /(a_i/) 代表序列每个值是多少。

输出格式

一行一个数字代表答案

样例

输入数据 1

7
2 0 2 1 2 0 5

输出数据 1

5

数据规模与约定

30% /(n<=5000/)
100% /(n<=1e5,~a_i<=1e6/)

Solution

这道题是经典的 /(/text{LIS}/) 问题的变形，在原来的 /(/text{LIS}/) 问题上，加入了 /(0/) 这个东西，本质上没有发生变化。

与普通的 /(/text{LIS}/) 问题相同，采用单调队列优化 /(/text{DP}/) 来实现。

令 /(f[i]/) 表示长度为 /(i/) 的最小 /(a[i]/) 的值，那么对于新加入的 /(a[i]/) ，如果不能接在队列末尾，那么就在队列中二分，查找第一个 /(f[i]/) 使得 /(f[i]>a[i]/) ，然后用 /(a[i]/) 更新这个答案。

对于 /(0/) 来说，不难发现，当 /(0/) 变成上一个数 /(+1/) 的时候是最佳的，因为此时 /(0/) 可以刚好接在队列末尾来使得 /(len++/)，如果变成小于这个值的数则无法更新最大值，不会是最优，如果更新为更大的值，可能导致后面的数无法接在当前这个 /(0/) 的后面，因此 /(0/) 变成上一个数 /(+1/) 时能保证结果最优。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<limits.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof(a));
using namespace std;
template<typename T> void read(T &k)
{
 	k=0;
	T flag=1;char b=getchar();
	while (b<'0' || b>'9') {flag=(b=='-')?-1:1;b=getchar();}
	while (b>='0' && b<='9') {k=(k<<3)+(k<<1)+(b^48);b=getchar();}
	k*=flag;
}
const int _SIZE=1e5;
int n;
int a[_SIZE+5],f[_SIZE+5];
int len;
int main()
{
	memset(f,0x7f,sizeof(f));
	read(n);
	for (int i=1;i<=n;i++) read(a[i]);
	f[0]=-INT_MAX;
	if (!a[1]) a[1]=-INT_MAX;
	for (int i=1;i<=n;i++)
	{
		int l=0,r=len;
		if (a[i]==0)
		{
			for (int j=len;j>=0;j--)
				f[j+1]=min(f[j]+1,f[j+1]);
			len++;
		}
		else
		{
			int l=0,r=len;
			while (l<r-1)
			{
				int mid=l+r>>1;
				if (f[mid]<a[i]) l=mid;
				else r=mid;
			}
			int j=0;
			if (a[i]>f[r]) j=r;
			else j=l;
			f[j+1]=min(f[j+1],a[i]);
			if (j+1>len) len=j+1;
		}
	}
	//for (int i=0;i<=len;i++) printf("%d ",f[i]);puts("");
	printf("%d/n",len);
	return 0;
}