先是nlogn的LIS解法
/* LIS nlogn解法 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; //结尾的数字越小，说明相同长度下当前序列越优 int lis[100005],a[100005];//lis[i]表示长度为i的最优的结尾数 int n,len=0; int find(int x){//找到lis中第一个大于等于x的数的下标 int l=0,r=len; while(l<r){ int mid=l+r>>1; if(lis[mid]>=x) r=mid; else l=mid+1; } return l; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); lis[1]=a[1];len++; for(int i=2;i<=n;i++){//按顺序处理每一个数 if(a[i]>lis[len])//可以更新新长度了 lis[++len]=a[i]; else{//对于一个a[i],可以更新以它为结尾的最长lis的结尾 int pos=find(a[i]);//找到lis中第一个大于等于a[i]的数，pos也是以那个数结尾的长度 lis[pos]=a[i]; //把那个数替换了 } } printf("%d ",len); return 0; }
线段树解LIS
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 10005 int len[maxn<<2]; int dp[maxn]; int a[maxn]; void build(int l,int r,int rt){ if(l==r){ len[rt]=0; return; } int m=l+r>>1; build(lson); build(rson); } void pushup(int rt){ len[rt]=max(len[rt<<1],len[rt<<1|1]); } void update(int pos,int val,int l,int r,int rt){ if(l==r){ len[rt]=val; return; } int m=l+r>>1; if(pos<=m) update(pos,val,lson); else update(pos,val,rson); pushup(rt); } int query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){ return len[rt]; } int m=l+r>>1; if(R<=m) return query(L,R,lson); else if(L>=m) return query(L,R,rson); return max(query(L,m,lson),query(m+1,R,rson)); } int main(){ int n; while(scanf("%d",&n)==1){ int temp=-1; memset(dp,0,sizeof dp); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); temp=max(temp,a[i]); } build(0,temp,1); int ans=0; //找到以小于a[i]的值为结尾的lis，值+1保存在dp[i]中,下一步再把这个dp值更新到线段树中 for(int i=1;i<=n;i++){ if(i!=1) update(a[i-1],dp[i-1],0,temp,1); if(a[i]>=1) dp[i]=query(0,a[i]-1,0,temp,1)+1; else dp[i]=1;//a[i]是0的情况 ans=max(ans,dp[i]); } printf("%d ",ans); } return 0; }
hdu4521 求间隔为d的lis
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define ll long long #define INF 0x3f3f3f3f #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define maxn 100010 int a[maxn],dp[maxn],n,d;//用dp存储以第i个数为结尾的lis int tree[maxn<<2];//保存以【l，r】结尾的lis inline void pushup(int rt){ tree[rt]=max(tree[rt<<1],tree[rt<<1|1]); } void build(int l,int r,int rt){ if(l==r){ tree[rt]=0; return; } int m=l+r>>1; build(lson); build(rson); pushup(rt); } //把val更新到pos位置,以pos值结尾的lis为val void update(int pos,int val,int l,int r,int rt){ if(l==r){ tree[rt]=val; return; } int m=l+r>>1; if(pos<=m) update(pos,val,lson); else update(pos,val,rson); pushup(rt); } //查询值在【L,R】之间的最大lis int query(int L,int R,int l,int r,int rt){ if(L<=l && R>=r){ return tree[rt]; } int m=l+r>>1,ret=-1; if(R<=m) return query(L,R,lson); else if(L>m) return query(L,R,rson); else return max(query(L,m,lson),query(m+1,R,rson)); // return ret; } int main(){ int temp,ans; while(scanf("%d%d",&n,&d)==2){ ans=temp=-1; memset(dp,0,sizeof dp); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); temp=max(temp,a[i]);//找到最大的值 } build(0,temp,1);//线段树的区间是0-temp,必须从0开始 for(int i=1;i<=n;i++){ if(i-d-1>=1)//必须相隔d+1及以上,把这个点更新进去 update(a[i-d-1],dp[i-d-1],0,temp,1); if(a[i]>=1)//找到之前更新以数值小于a[i]为结尾的最长lis dp[i]=query(0,a[i]-1,0,temp,1)+1; else dp[i]=1; ans=max(ans,dp[i]); } printf("%d ",ans); } }