P1439 [模板] 最长公共子序列 https://www.luogu.org/problemnew/show/P1439
此思路详见 luogu 第一个题解 一个很妙的离散化
刘汝佳蓝书上面的 LIS 详见蓝书
d[i] 以 i 为结尾的最长上升子序列的长度 g[i] 表示 d 值为 i 的最小状态的编号即长度为 i 的上升子序列的最小末尾值
- for(int i=1;i<=n;++i) scanf("%d",&a[i]);
- for(int i=1;i<=n;++i)
- {
- int k=lower_bound(g+1,g+1+n,a[i])-g;
- d[i]=k;
- g[k]=cb[i];
- }
只是手写二分的时候要注意超多细节 巨难受
- #include<bits/stdc++.h>
- using namespace std;
- #define rg register
- const int N=100000+5,inf=0x3f3f3f3f;
- int n,a[N],b[N],ca[N],cb[N];
- int g[N],d[N],len=0;
- template<class t>void rd(t &x)
- {
- x=0;int w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- x=w?-x:x;
- }
- int main()
- {
- rd(n);
- memset(g,inf,sizeof(g));
- for(rg int i=1;i<=n;++i) rd(a[i]),ca[a[i]]=i;
- for(rg int i=1;i<=n;++i) rd(b[i]),cb[i]=ca[b[i]];
- for(rg int i=1;i<=n;++i)
- {
- int k=lower_bound(g+1,g+1+n,cb[i])-g;
- g[k]=cb[i];
- len=max(len,k);
- }
- printf("%d",len);
- return 0;
- }
100 昏 用 lower_bound
- #include<bits/stdc++.h>
- using namespace std;
- #define rg register
- const int N=100000+5,inf=0x3f3f3f3f;
- int n,a[N],b[N],ca[N],cb[N];
- int g[N],len=0;
- template<class t>void rd(t &x)
- {
- x=0;int w=0;char ch=0;
- while(!isdigit(ch)) w|=ch=='-',ch=getchar();
- while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
- x=w?-x:x;
- }
- int find(int x)
- {
- int l=1,r=len,mid;
- while(l<=r)
- {
- mid=(l+r)>>1;
- if(x>g[mid]) l=mid+1;
- else r=mid-1;
- }
- return l;
- }
- int main()
- {
- rd(n);
- memset(g,inf,sizeof(g));
- for(rg int i=1;i<=n;++i) rd(a[i]),ca[a[i]]=i;
- for(rg int i=1;i<=n;++i) rd(b[i]),cb[i]=ca[b[i]];
- for(rg int i=1;i<=n;++i)
- {
- int k=find(cb[i]);
- g[k]=cb[i];
- len=max(len,k);
- }
- printf("%d",len);
- return 0;
- }
100 昏 手写二分
来源: http://www.bubuko.com/infodetail-3045005.html