题解：CF1647F Madoka and Laziness

· · 题解

题目传送门

题意

给定一个长度为 n 的序列 a，要求把这个序列分成两个子序列使得这两个子序列都为单峰序列，问有多少种划分方案，两种划分方案不同时，当且仅当存在一个序列的峰值不同。

思路

注意到，序列中每个数都不相同。所以，一定有一个子序列一直包含着序列中的最大值。所以方案数一定不会超过 n。我们钦定包含序列最大值的子序列为 A，另一个子序列为 B。由于序列最大值 x 会被包含在第一个序列中，我们假定第二个序列的峰值 y 在 x 的右边。那在左边的情况怎么办呢，把整个序列翻转，再操作一遍即可。

那么根据 x 和 y 的相对位置，我们可以把所有情况分为三种，如下图所示：

在 1\sim x 的区间内，序列 A 和序列 B 都上升，但是观察可知，因为序列 A 的峰值离 1 更近且峰值最大，所以在这段区间内我们要求让序列 A 上升的值尽可能的大，而序列 B 上升的值尽可能的小，这是为了满足 y 为峰值。

代码如下：

m1=m2=0;
for(int i=1;i<=pos;i++){
    if(a[i]>m1)m1=a[i];
    else if(a[i]>m2)m2=a[i];
    else return;
}

如果这个数可以给序列 A 那么就优先给序列 A,否则给序列 B。因为序列 A 的峰值最大，不用担心加入序列 A 的数会超过峰值。如果这个数都不能加入两个子序列那么说明这种情况不合法，直接返回。

同理，在 y\sim n 的区间内，序列 A 和序列 B 都下降。但是为了让当前 a_i 可能成为序列 B 的峰值，所以我们从后往前循环，用类似情况一的贪心策略，不过是让序列二尽可能大，这样 a_i 才有可能成为序列二的峰值为整个序列做贡献。

代码如下：

for(int i=n;i>pos;i--){
    if(a[i]>m2)m2=a[i];
    else if(a[i]>m1)m1=a[i];
    else break;
    dp1[i]=m1,dp2[i]=m2;
}

最后一种情况就是 x \sim y 的区间，这时 A 序列下降 B 序列上升，所以我们先考虑那种情况必须给 B 或给 B 更优，那么我们就把 a_i 给 B，否则给 A。同时判断答案是否合法。

代码如下：

for(int i=pos+1;i<=n;i++){
    if(a[i]>m2&&(a[i]>m1||a[i]<a[i+1]))m2=a[i];
    else if(a[i]<m1)m1=a[i];
    else break;
    ans+=(m1>dp1[i]&&m2<=dp2[i]);
}

最后不要忘记 把整个序列翻转，再做一遍。

完整代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010101;
const ll inf=1e18;
ll n,ans,a[N],dp1[N],dp2[N];
void solve(){
    ll pos=0,m1=0,m2=0;
    for(int i=1;i<=n;i++)dp1[i]=1e9,dp2[i]=0;
    for(int i=1;i<=n;i++)if(a[i]>a[pos])pos=i;
    for(int i=n;i>pos;i--){
        if(a[i]>m2)m2=a[i];
        else if(a[i]>m1)m1=a[i];
        else break;
        dp1[i]=m1,dp2[i]=m2;
    }
    m1=m2=0;
    for(int i=1;i<=pos;i++){
        if(a[i]>m1)m1=a[i];
        else if(a[i]>m2)m2=a[i];
        else return;
    }
    for(int i=pos+1;i<=n;i++){
        if(a[i]>m2&&(a[i]>m1||a[i]<a[i+1]))m2=a[i];
        else if(a[i]<m1)m1=a[i];
        else break;
        ans+=(m1>dp1[i]&&m2<=dp2[i]);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    solve();
    reverse(a+1,a+n+1);
    solve();
    cout<<ans<<'\n';
    return 0;
}