P6885 Zoltan 题解

Demeanor_Roy · 2022-09-20 15:29:25 · 题解

原题链接

前言

神仙 DP 题，建议评紫，考场上只能 30 分暴力走人，本篇题解便分别讲解一下 30 分和 100 分的做法。（之所以不讲 50 分，是因为它没有什么区分度，能想到这一步的人一般就能拿满了）

30 分做法

考虑枚举每一个可能序列，由于每一个新增元素只有放最左或放最右两种选择，所以一共只会有 2^n 种不同序列，对于每一个序列，我们用 n^2 统计最长严格上升子序列及其数量，就可以总体以 O(2^nn^2) 的复杂度解决问题，由于其实跑不满这么多，所以可以通过前 30 分。
枚举时有一个小技巧：我们可以用2进制从前到后枚举 2 到 n 号元素怎么放，如果其对应位上为 0，就代表当前元素放到左边，我们就将其放入一个栈中，否则将其放入一个队列中，而最终序列就是：依次从栈中取出元素加上一号元素加上依次从队列中取出元素，读者可以思考一下为什么是这样。
由于暴力比较简单，就不放代码了。

100 分做法

首先我们需要将原问题进行转化，这也是本题最难的地方。
具体来说，我们不可能对每一个可能序列都进行操作，因为单是枚举的时间我们都无法接受，那让我们思考一下，对于任意一个可能序列，它与给定序列有什么关系？如果你有着惊人的直觉，或许可以看出：每一个可能序列，都是由给定序列选择一个子序列沿一号元素“翻折”至左侧得到的。
这么说可能有些抽象，换种说法，就是从原序列中抽出一些数，将这些数顺次组成一个新序列，再翻转这个序列，拼接至最左侧得到的。（这一部分请读者仔细理解）
而有了这个结论，我们再回去看题就容易了许多：对于可能序列的一个最长严格上升子序列，一定是由原序列的一个严格下降子序列和一个严格上升子序列拼接而成的，当然需要满足的条件是前者的最大值严格小于后者的最小值且二者无交，我们发现这样并不好求，所以我们可以将前者新增一个元素：严格上升子序列的最小值。
这样转化之后，如果我们用 dp1(i) 和 dp2(i) 分别表示以 i 为开始的最长严格上升和下降子序列，那答案便是 \max(dp1(i)+dp2(i)-1)，其中 i 从 1 取到 n。
那接下来的问题就是如何求方案数，首先如果最长严格上升和下降子序列的个数分别为 cnt1(i) 和 cnt2(i) ，那对于确定的 i，子序列的个数显然是 cnt1(i) \times cnt2(i)，我们用 len 表示最长严格上升子序列长度（拼接后），这时我们来考虑其他元素怎么放：

综上所述，对于确定的 i，方案数为:
cnt1(i) \times cnt2(i) \times2^{n-len}
最后便是如何快速求最长严格上升子序列，相信大家都会 n^2 的做法，而树状数组优化也不难，这里就不细讲了。（注意不能用贪心加二分，因为那样不便于统计方案数）
放代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define lowbit(x) x&-x
const int N=2e5+10,mod=1e9+7;
int n,A[N];
LL ans1,ans2,dp1[N],dp2[N],cnt1[N],cnt2[N],fac[N];
vector<int> vec;
struct node
{
    int val;
    LL num;
    node()  {val=0,num=1;}
    inline void add(int x,LL y)
    {
        if(x>val)   val=x,num=y;
        else if(x==val) num=(num+y)%mod;
    }
}C1[N],C2[N];
inline void insert(int x,int y,LL z,node C[])
{
    for(;x<=n+1;x+=lowbit(x))   C[x].add(y,z);
}
inline node query(int x,node C[])
{
    node res;
    for(;x;x-=lowbit(x))    res.add(C[x].val,C[x].num);
    res.num=res.val?res.num:1;
    return res;
}
int main()
{
    scanf("%d",&n);
    fac[0]=1;
    for(int i=1;i<=n;i++)   fac[i]=fac[i-1]*2%mod;
    for(int i=1;i<=n;i++)   scanf("%d",&A[i]),vec.push_back(A[i]);
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    for(int i=1;i<=n;i++)   A[i]=lower_bound(vec.begin(),vec.end(),A[i])-vec.begin()+2;
    for(int i=n;i>=1;i--)
    {
        node up=query(n+1-A[i],C1),down=query(A[i]-1,C2);
        dp1[i]=up.val+1,cnt1[i]=up.num;;
        dp2[i]=down.val+1,cnt2[i]=down.num;
        insert(n+2-A[i],dp1[i],cnt1[i],C1);
        insert(A[i],dp2[i],cnt2[i],C2);
    }
    for(int i=1;i<=n;i++)   
    {
        int len=dp1[i]+dp2[i]-1;
        if(len>ans1)    ans1=len,ans2=cnt1[i]*cnt2[i]%mod*fac[n-len]%mod;
        else if(len==ans1)  ans2=(ans2+cnt1[i]*cnt2[i]%mod*fac[n-len]%mod)%mod;
    }
    printf("%lld %lld",ans1,ans2);
    return 0;   
}

完结撒花~