题目链接：hdu 5773 The All-purpose Zero
官方题解：0可以转化成任意整数，包括负数，显然求LIS时尽量把0都放进去必定是正确的。
因此我们可以把0拿出来，对剩下的做O(nlogn)的LIS，统计结果的时候再算上0的数量。
为了保证严格递增，我们可以将每个权值S[i]减去i前面0的个数，再做LIS，就能保证结果是严格递增的。
个人看法：对于显然把所以0放进去部分我解释一下：
- 如果0位于最长上升子序列两边，这两个零要加进去是显然的
- 如果有一个0夹于最长上升子序列之间，那么位于LIS中0左边的数应该比0右边的数小1，而因为预处理的效果，右边的数比左边的数至少大2，所以0是可以插进去的，举个例子：1 2 3 0 4 5 6->预处理后：1 2 3 0 3 4 5，最长是1 2 3 0 4（5） 5（6），括号里是原先的数，这个例子里0是替代了原序列0右边的4
- 有许多个0夹于LIS的，同理可得
/************************************************************** Problem:hdu 5773 The All-purpose Zero User: youmi Language: C++ Result: Accepted Time:171MS Memory:3148K ****************************************************************/ //#pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <set> #include <sstream> #include <cmath> #include <queue> #include <deque> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c) #define scs(a) scanf("%s",a) #define sclld(a) scanf("%I64d",&a) #define pt(a) printf("%d ",a) #define ptlld(a) printf("%I64d ",a) #define rep(i,from,to) for(int i=from;i<=to;i++) #define irep(i,to,from) for(int i=to;i>=from;i--) #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define lson (step<<1) #define rson (lson+1) #define eps 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl const double pi=4*atan(1.0); using namespace std; typedef long long ll; template <class T> inline void read(T &n) { char c; int flag = 1; for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0'; for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag; } int Pow(int base, ll n, int mo) { if (n == 0) return 1; if (n == 1) return base % mo; int tmp = Pow(base, n >> 1, mo); tmp = (ll)tmp * tmp % mo; if (n & 1) tmp = (ll)tmp * base % mo; return tmp; } //*************************** int n; const int maxn=200000+10; int a[maxn]; int val[maxn]; int c[maxn]; int tot; int lowbit(int x) { return x&(-x); } void update(int temp,int x) { while(x<=tot) { c[x]=Max(c[x],temp); x+=lowbit(x); } } int query(int x) { int res=0; while(x) { res=Max(c[x],res); x-=lowbit(x); } return res; } int main() { #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int T_T; scanf("%d",&T_T); for(int kase=1;kase<=T_T;kase++) { sc(n); zeros(c); int cnt=0; int tt=0; int u; rep(i,1,n) { sc(u); if(u==0) cnt++; else { a[tt]=u-cnt; val[tt]=a[tt]; tt++; } } sort(val,val+tt); tot=unique(val,val+tt)-val; int ans=0; rep(i,0,tt-1) { int temp=lower_bound(val,val+tot,a[i])-val+1; int res=query(temp-1)+1; ans=Max(ans,res); update(res,temp); } printf("Case #%d: %d ",kase,ans+cnt); } }