题意：
可以将0替换成任意interger（包括负数），在此基础上求最长递增子序列。
思路：
将所有的0全部提取出来，求出此时序列的LIS（不含0的），这是针对0在子序列的外面的情况，如0，1，2，3，0.那么如果0在子序列中间怎么办？
很简单，把读入的非0的数的值减去这个数前面0的个数即可，
如1，2，0，3，4。在提取出0后序列其实为1，2，2，3，LIS的长度为3，加上0的个数则为答案。
#include<bits/stdc++.h> using namespace std; #define N 100005 template <class T> inline void in(T &x) { T f = 1; char c; while ((c = getchar()) < '0' || c > '9') if (c == '-') f = -1; x = c - '0'; while ((c = getchar()) >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0'; x *= f; } int dp[N], sum[N], a[N], n; bool vis[N]; void solve(int kase) { in(n);sum[0]=0; memset(vis, false, sizeof(vis)); for(int i=1; i<=n; i++) { in(a[i]); if(a[i]==0) sum[i]=sum[i-1]+1, vis[i]=true; else sum[i]=sum[i-1], a[i]-=sum[i]; } int ans=sum[n], cnt=0; dp[0]=-1e9; for(int i=1; i<=n; i++) { if(vis[i]) continue; if(a[i]>dp[cnt]) dp[++cnt]=a[i]; else { int pos=lower_bound(dp, dp+cnt+1, a[i])-dp; dp[pos]=a[i]; } } ans+=cnt; printf("Case #%d: %d\n", kase, ans); } int main() { int t, kase=0;in(t); while(t--) { solve(++kase); } return 0; }
