洛谷 P1020 导弹拦截（递增子串 DP ）

题目大意：

有一个数列，我们要获取一组子串，这个子串必须单调不增。

问：

（1）最长 我们可以获取多长的这种子串

（2）这个数列中最多有多少种 这种子串

解题思路：

其中问题一是很典型的DP问题，最大不增子串。关键是第二问，我们要把第二问转一转思路，一种想法是贪心：我们每次都从这个串抽出单调不增子串，看能抽取多少次，但是假如这样抽取的话，可以试一下这个样例：

1000 1005 999 998 1004

第二问：输出2是对的 ，分别是 1000 999 998，1005 1004这两个子串。

假如按照贪心抽取的话，结果会是1005 999 998 ,1000,1004这三个子串。原因在于第一个子串的第一个数字取到了1005.

第二种想法：找单调递增子串

这种想法可行是因为，在这个单调递增子串中不存在 单调不增子串，所以这个单调递增子串每个元素都是 所有单调不增子串的首个元素！而且已经是最优，不存在更多的单调不增子串。

关于这种子串应该怎么找。

我们以单调递增子串为例。本质上，我们最后必须通过一个链表输出，所以我们要维护一个链表。另外，我们还要维护一个序列，这个序列有个特点：单调递增。大概流程：

arr 是数列的元素
L=[]
for i in arr:
    pos=lower_bound(L，L+lis，i)    找出在L中大于等于i的第一个数字的下标
注意在这里，假如我们要找单调不减子串，那么我们必须找到的是 大于等于i的这个数字的下一个下标
...
    L[pos]=i    更新L，重要！
    L_id[pos]=i    
    P[i]=pos==0?-1:L_id[pos-1]    更新P，重要！
...

其中比较重要的是理解为什么链表要这样指，其实这是一种有点类似于贪心的做法，我们指向的是已知的最邻近的比当前小的元素。

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;
int L[MAXN];
int Arr[MAXN];
int mybsearch(int l,int r,int val){
  while(l<r){
    int m=l+(r-l)/2;
    if(L[m]<val)r=m;
    else if(L[m]>=val)l=m+1;
  }
  assert(l==r);
  return l;
}
int main(){
  int n=0;
  while(cin>>Arr[n]){
    n++;
  }
  int lis;int lis_end;
  int L_id[MAXN];
  int P[MAXN];
  int finans=0;
  lis=0;
  L[0]=-1;
  for(int i=0;i<n;i++){
    int pos=mybsearch(0,lis,Arr[i]);
    L[pos]=Arr[i];
    L_id[pos]=i;
    P[i]=pos!=0?L_id[pos-1]:-1;
    if(pos+1>lis){
      lis+=1;
      lis_end=i;
    }
  }
  for(int poi=lis_end;poi!=-1;poi=P[poi]){
    finans++;
  }
  int LIS=0;
  lis=0;
  for(int i=0;i<n;i++){
    int pos=lower_bound(L,L+lis,Arr[i])-L;
    L[pos]=Arr[i];
    L_id[pos]=i;
    P[i]=pos!=0?L_id[pos-1]:-1;
    if(pos+1>lis){
      lis=pos+1;
      lis_end=i;
    }
  }
  for(int poi=lis_end;poi!=-1;poi=P[poi]){
    LIS++;
  } 
  cout<<finans<<endl;
  cout<<LIS<<endl;
  return 0;
}