其实之前做过一次,结果忘了。。。

基础不牢地动山摇,

没了

---

LIS:

代码:

1 #include
     
       2 #define gc getchar 3 #define R register int 4 using namespace std; 5 int a[100005],d[100005],len; 6 inline int rd() 7 { 8     int ans=0,flag=1; 9     char ch=gc();10     while((ch<'0'||ch>'9')&&ch!='-')ch=gc();11     if(ch=='-')flag=-1,ch=gc();12     while(ch>='0'&&ch<='9')ans=ans*10+(ch^48),ch=gc();13     return ans*flag;14 }15 int main()16 {17     int n;18     n=rd();19     for(R i=1;i<=n;i++)20     {21         a[i]=rd();22     }23     d[1]=a[1];len=1;24     for(R i=2;i<=n;i++)25     {26         if(a[i]>d[len])27         {28             d[++len]=a[i];29         }30         else31         {32             int t=lower_bound(d+1,d+len+1,a[i])-d;33             d[t]=a[i];34         }35     }36     cout<
      
       <
      
     

有时间再来upd吧