70分代码：（n^2 LIS）
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; int n,nor[100010],sou[100010],c[100010],q[100010],dp[100010],ans=0; int main(){ memset(q,0,sizeof(q)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&nor[i]); for(int i=1;i<=n;i++){ scanf("%d",&sou[i]); } for(int i=1;i<=n;i++) { c[i]=find(sou,sou+n,nor[i])-sou; //printf("c[%d]=%d\n",i,c[i]); } for(int i=1;i<=n;i++){ dp[i]=1; for(int j=1;j<i;j++) if(c[j]>c[i]) dp[i]=max(dp[i],dp[j]+1); ans=max(ans,dp[i]); } printf("%d",ans); return 0; }把最长不上升子序列优化到O(nlogn)的思路：
1、对于长度为k的最长不上升子序列，用数组q[k]记录其末尾数字（即序列中最小数字）的最大值
2、对于k1>k2，可以知道其q[k1]<q[k2]
3、所以对于当前待考虑的数字a[i]，到i以前的最长不上升子序列长度为p，分如下两种情况讨论：
①如果a[i]<=q[p]，可以直接将a[i]加入，d[i]=p+1，更新q[p+1]=a[i]
②如果a[i]>q[p]，用upper_bound找到q数组中第一个不小于a[i]的q[p']，d[i]=p'+1，更新q[p'+1]=a[i]
转载于:https://www.cnblogs.com/leotan0321/p/6081424.html
