[BZOJ5427]最长上升子序列

考虑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
",tot+add);
28     return 0;
29 }