最长上升子序列(LIS)长度及其数量

本是古典何须时尚 2021-10-26 15:16 358阅读 0赞

例题51Nod-1376，一个经典问题，给出一个序列问该序列的LIS以及LIS的数量。

这里我学习了两种解法，思路和代码都是参考这两位大佬的：

[https://www.cnblogs.com/reverymoon/p/9496040.html][https_www.cnblogs.com_reverymoon_p_9496040.html]

[https://www.cnblogs.com/RabbitHu/archive/2017/11/02/51nod1376.html][https_www.cnblogs.com_RabbitHu_archive_2017_11_02_51nod1376.html]

首先是先分析一下问题，求LIS是一个很基础的问题了，用得最多的是nlogn的解法这里就不讲了。当我们求出序列a\[i\]的LIS为f\[i\]时，我们应该从哪里得到LIS的数量s\[i\]呢？

显然应该是 s\[i\]=sigma(s\[j\])（j<i，a\[j\]<a\[i\]，f\[j\]=f\[i\]-1），即满足这三个条件的s\[j\]的和。因为我们是从左到右做，所以第一个条件满足，然后问题就是怎么能快速找到a\[j\]<a\[i\]且f\[j\]=f\[i\]-1的s\[j\]的和呢？

这里博主学习到两种解法，先将树状数组解法：将离散化后的a\[i\]作为下标在树状数组上建树，那么此时a\[i\]的前缀就必定满足a\[j\]<a\[i\]了，同时树状数组维护的是以a\[i\]结尾的LIS长度f\[i\]和a\[i\]的LIS数量s\[i\]。当求解a\[i\]时，我们在BIT上查询a\[i\]-1前缀的最长LIS同时累加最长LIS的数量，那么**返回的结果就是后面一个数可以接上a\[i\]这个数的最长LIS和它的数量（**这句话是重点**）**。所以f\[i\]=返回结果+1，s\[i\]=返回结果数量。代码实现是学习上面博客大佬，带有一些小技巧。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int N=5e4+10;
     4 const int P=1e9+7;
     5 int n,m,a[N],b[N];
     6 struct dat{
     7     int len,sum;
     8 }bit[N],dp[N];
     9 
    10 void upd(dat &x,dat y) {  //计算y对x的影响 
    11     if (x.len>y.len) return;
    12     else if (x.len<y.len) x=y;
    13     else x.sum+=y.sum,x.sum%=P;
    14 }
    15 
    16 void update(int x,dat v) {
    17     for (;x<=m;x+=x&-x) upd(bit[x],v);
    18 }
    19 
    20 dat query(int x) {
    21     dat ret=(dat){
         0,1};
    22     for (;x;x-=x&-x) upd(ret,bit[x]);
    23     return ret;
    24 }
    25 
    26 int main()
    27 {
    28     cin>>n;
    29     for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
    30     sort(b+1,b+n+1);
    31     m=unique(b+1,b+n+1)-(b+1);
    32     for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
    33     //update(0,(dat){0,1});  不能这样写会死循环 
    34     for (int i=1;i<=n;i++) {
    35         dp[i]=query(a[i]-1); dp[i].len++;
    36         update(a[i],dp[i]);
    37     }
    38     dat ans=(dat){
         0,0};
    39     for (int i=1;i<=n;i++) upd(ans,dp[i]);
    40     cout<<ans.sum<<endl;
    41     return 0;
    42 }

然后是同一道题的Vector+二分的解法。这种解法会更加容易理解，还是看上面三个条件（j<i，a\[j\]<a\[i\]，f\[j\]=f\[i\]-1），然后第一个条件不用管考虑后两个条件。在学习nlogn的LIS解法的时候应该有学习到：从左到右同等长度的LIS末尾数字应该是单调不增的，基于这个我们可以考虑**把前面的a\[j\]按照f\[j\]大小分组**，同等LIS长度的元素a\[j\]存在同一个vector里面，然后这个vector的元素应该是单调不增的，那么我们就可以通过二分查找在f\[i\]-1的这一个vector里面快速地找到所有的<a\[i\]的元素，同时也就是快速算出满足上诉三个条件的s\[j\]总和。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int N=5e4+10;
     4 const int P=1e9+7;
     5 const int INF=0x3f3f3f3f;
     6 int n,m,a[N],g[N],f[N],s[N];
     7 vector<int> len[N],sum[N];  //len[i]存放LIS为i的数a[i],sum[i]存放a[i]对应的LIS数量 
     8 //显然len[i]的元素是单调不增的 
     9 
    10 int Find(int p,int x) {  //二分len=p的最后一个>=x的位置,这个位置后面的就是答案 
    11     int l=0,r=len[p].size()-1,mid;
    12     while (l<r) {
    13         mid=l+r+1>>1;
    14         if (len[p][mid]>=x) l=mid;
    15         else r=mid-1;
    16     }
    17     return ((sum[p].back()-sum[p][l])%P+P)%P;
    18 }
    19 
    20 int main()
    21 {
    22     cin>>n;
    23     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    24     memset(g,0x3f,sizeof(g));
    25     for (int i=0;i<=n;i++) len[i].push_back(INF),sum[i].push_back(0);
    26     len[0].push_back(-INF),sum[0].push_back(1);
    27     int Max=0,ans=0;
    28     for (int i=1;i<=n;i++) {
    29         int t=lower_bound(g+1,g+n+1,a[i])-g;
    30         g[t]=a[i];
    31         f[i]=t; s[i]=Find(t-1,a[i]);
    32         len[t].push_back(a[i]); sum[t].push_back((sum[t].back()+s[i])%P);
    33         
    34         if (f[i]>Max) Max=f[i],ans=s[i];
    35         else if (f[i]==Max) ans=(ans+s[i])%P;
    36     }
    37     cout<<ans<<endl;
    38     return 0;
    39 }

题目练习：

2019计蒜之道 复赛 外教 Michale 变身大熊猫：[https://nanti.jisuanke.com/t/39611][https_nanti.jisuanke.com_t_39611]

容易想到a\[i\]会在LIS的概率就是：(必须经过a\[i\]的LIS数量)/(所有的LIS数量)  。所有的LIS数量好求，主要问题就是怎么求必须经过a\[i\]的LIS的数量，这个问题也不难想，就是  从左到右以a\[i\]结尾的LIS数量\*从右到左为a\[i\]为结尾的最长下降子序列数量。这就用到上面的知识了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 const int P=998244353;
     4 const int N=5e5+10;
     5 typedef long long LL;
     6 int n,m,a[N],b[N],c[N];
     7 
     8 struct dat{
     9     int len,sum;
    10 }dp1[N],dp2[N],bit[N];
    11 void upd(dat &x,dat y) {
    12     if (x.len>y.len) return;
    13     else if (x.len<y.len) x=y;
    14     else x.sum+=y.sum,x.sum%=P;
    15 }
    16 void update(int x,dat v) {
    17     for (;x<=m;x+=x&-x) upd(bit[x],v);
    18 }
    19 dat query(int x) {
    20     dat ret=(dat){
         0,1};
    21     for (;x;x-=x&-x) upd(ret,bit[x]);
    22     return ret;
    23 }
    24 
    25 int power(int x,int p) {
    26     int ret=1;
    27     for (;p;p>>=1) {
    28         if (p&1) ret=((LL)ret*x)%P;
    29         x=((LL)x*x)%P;
    30     }
    31     return ret;
    32 }
    33 
    34 int main()
    35 {
    36     cin>>n;
    37     for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];
    38     sort(b+1,b+n+1);
    39     m=unique(b+1,b+n+1)-(b+1);
    40     for (int i=1;i<=n;i++) c[i]=lower_bound(b+1,b+m+1,a[i])-b;
    41     
    42     dat ans=(dat){
         0,0};
    43     memset(bit,0,sizeof(bit));
    44     for (int i=1;i<=n;i++) {
    45         dp1[i]=query(c[i]-1); dp1[i].len++;
    46         update(c[i],dp1[i]);
    47         upd(ans,dp1[i]);
    48     }
    49     
    50     for (int i=1;i<=n;i++) c[i]=m-c[i]+1;
    51     memset(bit,0,sizeof(bit));
    52     for (int i=n;i;i--) {
    53         dp2[i]=query(c[i]-1); dp2[i].len++;
    54         update(c[i],dp2[i]);
    55     }
    56     
    57     for (int i=1;i<=n;i++)
    58         if (dp1[i].len+dp2[i].len-1==ans.len) {
    59             int t=(LL)dp1[i].sum*dp2[i].sum%P*power(ans.sum,P-2)%P;
    60             printf("%d ",t);
    61         } else printf("0 ");
    62     return 0;
    63 }

转载于:https://www.cnblogs.com/clno1/p/11212531.html

[https_www.cnblogs.com_reverymoon_p_9496040.html]: https://www.cnblogs.com/reverymoon/p/9496040.html
[https_www.cnblogs.com_RabbitHu_archive_2017_11_02_51nod1376.html]: https://www.cnblogs.com/RabbitHu/archive/2017/11/02/51nod1376.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/fee6256a76244e00a7725dcdc965b332.png
[https_nanti.jisuanke.com_t_39611]: https://nanti.jisuanke.com/t/39611