HDU 5141-白红宇

HDU 5141

阅读量：5318 次

发布时间：2019-06-14

本文共 1043 字，大约阅读时间需要 3 分钟。

这个题 LIS + 并查集的思想 + 链式前向星

要求找s(i,j)使i j 能有最长的LIS 。。。

做法是枚举每一个j 即终点算起点的可能

无力吐槽了 bc 的时候写错了一个地方导致TLE 后来幡然醒悟了

改了就a了

+++++++++++++++++++++++++++++++++++++++++++

不想说什么了直接上代码

+++++++++++++++++++++++++++++++++++++++++++

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #define CL(a,b) memset(a,b,sizeof(a))#define ll __int64#define TEST cout<<"TEST ***"<
               
                =v&&so[m-1]
                
                 v)return bin(s,m,v); return bin(m+1,e,v);}int main(){ while(scanf("%d",&n)!=EOF) { int i,j,a,p,v; initfa(); inithead(); so[0]=-1;ct=0; for(i=1;i<=n;i++) { scanf("%d",&a); num[i]=a; if(a>so[ct]) { ct++; so[ct]=a; addnode(ct,i); pi[i]=ct; } else { p=bin(0,ct,a); so[p]=a; addnode(p,i); pi[i]=p; } if(pi[i]!=1) { p=head[pi[i]-1]; while(p!=-1) { v=no[p].p; if(num[v]
                 
                  =1) { la++; if(pi[i]==ct) { he=finr(i); rem+=la*he; la=0; } i--; } printf("%I64d\n",rem); } return 0;}