考虑O(n log n)的LIS求法，dp[i]表示到目前为止，长度为i的LIS的末尾最小是多少。
当当前数确定时直接用LIS的求法更新dp数组，当不确定时，由于这个数可以是任意数，所以可以接在任意上升子序列后面，于是相当于所有dp[i]=min(dp[i],dp[i-1]+1)，也就是整个数组+1后右移一位。这个记录一个增量即可，复杂度与普通LIS一样。
1 #include<cstdio> 2 #include<algorithm> 3 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 4 using namespace std; 5 6 const int N=100010; 7 int n,x,add,tot,dp[N]; 8 char ch; 9 10 int main(){ 11 freopen("bzoj5427.in","r",stdin); 12 freopen("bzoj5427.out","w",stdout); 13 dp[0]=-1e9; scanf("%d",&n); 14 rep(i,1,n){ 15 scanf(" %c",&ch); 16 if (ch==‘N‘) add++; 17 else{ 18 scanf("%d",&x); 19 int L=0,R=tot,res; 20 while (L<=R){ 21 int mid=(L+R)>>1; 22 if (dp[mid]+add<x) L=mid+1,res=mid; else R=mid-1; 23 } 24 if (res==tot) dp[++tot]=x-add; else dp[res+1]=min(dp[res+1],x-add); 25 } 26 } 27 printf("%d\n",tot+add); 28 return 0; 29 }
原文：https://www.cnblogs.com/HocRiser/p/9910458.html