题目链接：

 

这里说下，最长上升子序列和最长不降子序列几乎一样，只是判断=的时候注意一下。另外最长不降子序列经常反过来考，有几个最长不降，而不是求它的长度。（经典例题导弹拦截系统）

 

分析和思路：

 我们维护当前最长的长度len,用vis[j]存储长度为j的所有子序列中最小的末尾数值,那么对于当前数据a[i],如果数组vis中存在比其大的元素我们用a[i]替换掉vis中第一个比a[i]大的数,若不存在,那么我们将a[i]加入vis末尾,此时数组长度+1,如此我们便维护了数组vis的性质,最终得到的len就是答案了.因为数组vis再加入时就保持了递增的性质,所以在查找时可以用二分查找函数lower_bound把时间复杂度降到n*logn。

 

当然这题不用二分函数也可以过，其实我反而觉得不用函数更好（当然再不超时的前提下），自己一步一步的慢慢实现这个过程能极大的帮助理解这个方法（算法）的本质，体会到它的巧妙（当初仔细想了几遍，想通了巧妙之后发现它是如此有趣^^），过段时间后也不会轻易忘记 。

这个题是要求严格递增子序列（ps:这类题<=或<的地方要区分清楚理解清楚）

1 #include 
     
       2 using namespace std; 3 const int maxn=1e6+5; 4 int a[maxn],vis[maxn]; 5 int main() 6 { 7       int n; 8       cin>>n; 9       for(int i=1;i<=n;i++) cin>>a[i];10       for(int i=0;i<=n;i++) vis[i]=-1e9-1;11       12       vis[1]=a[1];int len=1;13       for(int i=2;i<=n;i++)14       {15           int f=0;16           for(int j=1;j<=len;j++)//
     

 

还有一道极类似题，hdu最少拦截系统，

分析和思路：

其实就是把lis反过来理解，代码都不用变！只不过这个思维转换的过程不好想，我也是看了别人说的之后才转换过来想通。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5 const int maxn=1e6+5;  6 int a[maxn],b[maxn],vis[maxn]; 7 int main() 8 { 9     ios::sync_with_stdio(false);cin.tie(0);10      11     int n;12     while(cin>>n)13     {14          for(int i=1;i<=n;i++) cin>>a[i];15          for(int i=0;i<=n;i++) vis[i]=-1e9-1;16      17          vis[1]=a[1];int len=1;18          for(int i=2;i<=n;i++)19          {20              int f=0;21              for(int j=1;j<=len;j++)22              {                      //=重要!把相等时(不用再开一套系统)也要装进去(代表非严格递降，即不高于)23                  if(a[i]<=vis[j])//如果<,则是严格递降,是高于 24                  {                  //与lis意义不同,高度降低代表当前这套的最大高度 25                      f=1;26                      vis[j]=a[i];27                      break;28                  }29              }30              if(!f) vis[++len]=a[i];//与lis意义不同，代表增加一套系统（lis是存的那一条最长递增列） 31          }32          cout<
        
         <
        
       
      
     

 

洛谷上述两个，https://www.luogu.org/problemnew/show/P1020

反着正着都考了，同时更新为二分查找做法

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #define sc(x) scanf("%d",&x) 7 #define pr(x) printf("%d",x) 8 #define ppp putchar('\n') 9 using namespace std;10 const int maxn=1e6+5; 11 int a[maxn],vis[maxn],viss[maxn];12 int main()13 {14     int n=1;15     while(sc(a[n])!=EOF) n++;16     n--;17     for(int i=0;i<=n;i++) vis[i]=-1e9-1;18     19     int len1=1; 20     vis[1]=a[1];21     for(int i=2;i<=n;i++)22     {23         /*for(int j=1;j<=len1;j++)24         {                      25             if(a[i]<=vis[j]) 26             {27                 f1=1;28                 vis[j]=a[i];29                 break;30             }31         }*/32  33         int f1=lower_bound(vis+1,vis+1+len1,a[i])-(vis+1)+1;34         if(f1<=len1) vis[f1]=a[i];35         else vis[++len1]=a[i]; 36     }37     38     reverse(a+1,a+1+n);39     int len2=1; 40     viss[1]=a[1];41     for(int i=2;i<=n;i++)42     {43         /*for(int j=1;j<=len2;j++)44         {                      45             if(a[i]
         
        
       
      
     

 

完