这题想了1个多小时想不出来...方法真是精妙...
官方题解：0可以转化成任意整数，包括负数，显然求LIS时尽量把0都放进去必定是正确的。因此我们可以把0拿出来，对剩下 的做O(nlogn)的LIS，统计结果的时候再算上0的数量。为了保证严格递增，我们可以将每个权值S[i]减去i前面0的个 数，再做LIS，就能保证结果是严格递增的。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> #include<map> #include<set> #include<queue> #include<stack> #include<iostream> using namespace std; typedef long long LL; const double pi=acos(-1.0),eps=1e-8; void File() { freopen("D:\in.txt","r",stdin); freopen("D:\out.txt","w",stdout); } inline int read() { char c = getchar(); while(!isdigit(c)) c = getchar(); int x = 0; while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x; } const int maxn=100000+10; int T,n,a[maxn],sum[maxn],dp[maxn]; int t[80*maxn]; void update(int p,int val,int l,int r,int rt) { if(l==r) { t[rt]=max(val,t[rt]); return; } int m=(l+r)/2; if(p<=m) update(p,val,l,m,2*rt); else update(p,val,m+1,r,2*rt+1); t[rt]=max(t[2*rt],t[2*rt+1]); } int get(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) return t[rt]; int m=(l+r)/2,maxL=0,maxR=0; if(L<=m) maxL=get(L,R,l,m,2*rt); if(R>m) maxR=get(L,R,m+1,r,2*rt+1); return max(maxL,maxR); } int main() { scanf("%d",&T); int cas=1; while(T--) { memset(dp,0,sizeof dp); memset(sum,0,sizeof sum); memset(t,0,sizeof t); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { sum[i]=sum[i-1]; if(a[i]==0) sum[i]++; } for(int i=1;i<=n;i++) { if(a[i]==0) continue; a[i]=a[i]-sum[i]+1000000; if(a[i]!=0) dp[i]=get(0,a[i]-1,0,2000000,1)+1; else dp[i]=1; update(a[i],dp[i],0,2000000,1); } int Max=0; for(int i=1;i<=n;i++) Max=max(Max,dp[i]); printf("Case #%d: %d ",cas++,Max+sum[n]); } return 0; }