LIS-二分查找模版

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int dp[100005];char a[100005]; int Lis(int n) { int len=1,i,low,high,mid; dp[1]=a[1]; for(i=2;i<=n;i++) { low=1; high=len; while(low<=high) { mid=(low+high)/2; if(a[i]>dp[mid]) low=mid+1; else high=mid-1; } dp[low]=a[i]; if(low>len) len=low; } return len; } int main() { int t; scanf("%d",&t); for(int cas=1;cas<=t;cas++) { scanf("%s",a+1); int ans=Lis(strlen(a+1)); printf("Case #%d: %d\n",cas,ans); } } #include <cstdio> #include <algorithm> using namespace std; int a[50005],dp[50005]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[1]=a[1]; int len=1; for(int i=2;i<=n;i++) if(a[i]>dp[len]) dp[++len]=a[i]; else { int pos=lower_bound(dp+1,dp+len+1,a[i])-dp; dp[pos]=a[i]; } printf("%d\n",len); }