求最长公共子序列的长度，用普通的方法会超时。 用二分的方法找他插入的位置，如果在最后，那么就插入到最后，否则就在第一个大于它的地方插入（严格递增子序列这样求，如果在第一个大于它的地方就是不下降子序列了，对应两个方法） 挑战程序设计2上的代码实现更好。哈哈
顺便讲一下LIS的变形。 1 正常求LIS，这谁不会啊，直接板板美滋滋，具体思路是，用暴力的方法求LIS，之所以不可以就是因为诸如 1 7 2 3 4 之类的，选7直接蒙蔽，构成子序列 1 7 显然不是最大的，最好的方法如果7大于2，这时在子序列里二分第一个大于他的（很猛先这是不严格的上升），就替换。 2 求下降子序列，就把序列反转一下就行，当然你求的dp数组也要反转哦。 3 求以i为开头的 LIS，先反转，在变成负数。 4 求以i为开头的下降， 就先反转，在反转，在变成负数（反转个毛线。。） 具体看图。图1时正常LIS。图3时以i为底的LIS 给个例题 https://blog.csdn.net/qq_35781950/article/details/71273679
#include <iostream> #include <cstdio> using namespace std; /* 开心，看了两天终于看懂了。 之前 不怎么确定的地方有下面这些方面， 这道题其实特别简单，求一下严格的最长公共子序列， 然后在求一下严格的下降子序列（咋求下降子序列啊哈哈） */ #define INF 0x3f3f3f3f int main() { int m; int a[50006]; int dp[50006]; while(cin>>m) {for(int i=0;i<m;i++) cin>>a[i]; fill(dp,dp+m,INF);//全部初始化为无穷大，不用比较就找到了端点。 for(int i=0;i<m;i++) *lower_bound(dp,dp+m,a[i])=a[i]; printf("%d\n",lower_bound(dp,dp+m,INF)-dp); } return 0; } #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <vector> using namespace std; int main() { int t; int m; int a[50006]; int dp[50006]; memset(dp,0,sizeof(dp)); while(cin>>m) { for(int i=0;i<m;i++) { cin>>a[i]; } vector<int>q; for(int i=0;i<m;i++) { int u=upper_bound(q.begin(),q.end(),a[i])-q.begin(); if(u==q.size()) { q.push_back(a[i]); dp[i]=q.size(); } else { q[u]=a[i]; dp[i]=u+1; } } int big=-1; for(int i=0;i<m;i++) big=max(big,dp[i]); printf("%d\n",big); //for(int i=0;i<q.size();i++) //printf("%d ",q[i]); } return 0; }nefu1424 这个，，我错了好几次，粗心。。 你们看代码就懂了，我浑身难受。
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include <cstring> using namespace std; const int maxn=1e5+5; int dp[maxn]; int dp2[maxn]; int m; void solve(vector<int>q){ vector<int>a; for(int i=0;i<q.size();i++){ int u=lower_bound(a.begin(),a.end(),q[i])-a.begin(); if(u==a.size()){ a.push_back(q[i]); dp[i]=max(dp[i],(int)a.size()); } else{ a[u]=q[i]; dp[i]=max(u+1,dp[i]);//维护max无意义，直接等就好 } } } void solve2(vector<int>q){ vector<int>a; for(int i=0;i<q.size();i++){ int u=lower_bound(a.begin(),a.end(),q[i])-a.begin(); if(u==a.size()){ a.push_back(q[i]); dp2[i]=max((int)a.size(),dp2[i]); } else{ a[u]=q[i]; dp2[i]=max(u+1,dp2[i]); } } reverse(dp2,dp2+m); } int main() { int a; vector<int>q; while(cin>>m){ //if(!m)break; q.clear(); for(int i=0;i<m;i++) { dp[i]=dp2[i]=0; } for(int i=0;i<m;i++){ cin>>a; q.push_back(a); } solve(q); reverse(q.begin(),q.end()); solve2(q); int ans=-1; for(int i=0;i<m;i++){ //cout<<dp[i]<<" "<<dp2[i]<<endl; //if(dp[i]==dp2[i]) ans=max(ans,2*min(dp[i],dp2[i])-1); } cout<<ans<<endl; } return 0; }