<span>HDU5773 The All-purpose Zero（LIS）</span>
题意：
给你一个长度为10W的数组，每个数范围0-100W
其中的0可以变为INT范围内的任意值
问最长上升子序列的长度
思路：
这题当时水过了。。数据太水
比赛结束了看了题解，简直膜拜神思路。。
0可以转化成任意整数，包括负数，
显然求LIS时尽量把0都放进去必定是正确的。
因此我们可以把0拿出来，对剩下的做O(nlogn)的LIS，
统计结果 的时候再算上0的数量。为了保证严格递增，
我们可以将每个权值S[i]减去i前面0的个数，
再做LIS，就能保证结果是严格递增的。
照着这题解写了一发AC了
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=1e5+10; int a[N],ans[N]; int main() { //freopen("in.txt","r",stdin); int t,m,x; scanf("%d",&t); for(int cas=1;cas<=t;cas++) { scanf("%d",&m); int cnt=0,n=0; for(int i=1;i<=m;i++) { scanf("%d",&x); if(!x) cnt++; else a[++n]=x-cnt; } if(!n) { printf("Case #%d: %d\n",cas,m); continue; } ans[1]=a[1]; int len=1; for(int i=2;i<=n;i++) { if(a[i]>ans[len]) ans[++len]=a[i]; else { int pos=lower_bound(ans+1,ans+len,a[i])-ans; ans[pos]=a[i]; } } printf("Case #%d: %d\n",cas,len+cnt); } return 0; }
