[Codeforces261D]Maxim and Increasing Subsequence—

[Codeforces261D]Maxim and Increasing Subsequence——树状数组+DP

阅读量：4557 次

发布时间：2019-06-08

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

题目链接：

题目大意：$k$次询问，每次给出一个长度为$n$的序列$b$及$b$中的最大值$maxb$，构造出序列$a$为$t$个序列$b$连接而成，求$a$的最长上升子序列。$n,maxb\le10^5,maxbn\le210^7,t\le10^9$。

设$b$中不同数的个数为$sum$。如果$sum\le t$，那么答案就是$sum$(只需要从第$i$个序列$b$中取第$i$小的数即可)。现在只需要考虑$t<sum$的情况，因为$sum\le maxb$，所以$t<maxb$，这也就说明$n*t<n*maxb=2*10^7$，那么序列长度最大为$2*10^7$，我们只需要$O(nlog_{n})$求序列的最长上升子序列即可。直接$DP$，$f[i]$表示前$i$个数的最长上升子序列长度，用树状数组存前缀最大值然后扫一遍整个序列$DP$即可。

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;int sum;int n,t,k;int b[100010];int a[20000010];int v[100010];int ans;int maxb;int f[20000010];map
                
                 mp;void add(int x,int k){ for(int i=x;i<=maxb;i+=i&-i) { v[i]=max(v[i],k); }}int ask(int x){ int res=0; for(int i=x;i;i-=i&-i) { res=max(res,v[i]); } return res;}int main(){ scanf("%d%d%d%d",&k,&n,&maxb,&t); while(k--) { memset(v,0,sizeof(v)); mp.clear(); sum=0; ans=0; for(int i=1;i<=n;i++) { scanf("%d",&b[i]); if(!mp[b[i]]) { sum++; mp[b[i]]=1; } } if(t>=sum) { printf("%d\n",sum); continue; } for(int i=1;i<=n*t;i++) { a[i]=b[(i-1)%n+1]; } for(int i=1;i<=n*t;i++) { f[i]=ask(a[i]-1)+1; ans=max(ans,f[i]); add(a[i],f[i]); } printf("%d\n",ans); }}

转载于:https://www.cnblogs.com/Khada-Jhin/p/10441696.html

你可能感兴趣的文章

题目链接：

题目大意：$k$次询问，每次给出一个长度为$n$的序列$b$及$b$中的最大值$maxb$，构造出序列$a$为$t$个序列$b$连接而成，求$a$的最长上升子序列。$n,maxb\le10^5,maxb*n\le2*10^7,t\le10^9$。

题目大意：$k$次询问，每次给出一个长度为$n$的序列$b$及$b$中的最大值$maxb$，构造出序列$a$为$t$个序列$b$连接而成，求$a$的最长上升子序列。$n,maxb\le10^5,maxbn\le210^7,t\le10^9$。