题解：CF1647F Madoka and Laziness

· · 题解

题目分析

把一个序列分割成相对位置不变的两个序列，求这两个序列的峰的不同组合方案数。

说了跟说了是的。

解题思路

可以先去看看这道题 CF1144G，把这道题通过了之后说不定就会写了。

再来观察题目，可以发现，不管怎么分割，必然有一个子序列的峰是整个序列的最大值，因为你不可能把这个最大值丢了不要。

那么我们只需要考虑另一个子序列的峰就好了，显而易见，答案一定小于 n。

在整个序列中找到最大值 mx，枚举其他的数 y，判断其能否作为另一个序列的峰。

先约定 y 位于 mx 右边。

至于在左边的情况，将序列反转一下就好了。别问为什么是右边。

如下图所示：

分为三个部分，其实前后两个部分实质是一样的，可以归为一类。

在做过 CF1144G 这道题后你就会恍然大悟。

设计状态

状态如何转移

注意：时刻记住 f1_i 维护的是红色递增序列最右端的最小值，而不是黑色的。

注意细节

  1. 注意转移方程的初始值，看情况设为无穷大或着无穷小。

  2. 在三个转移方程都处理完之后，需要对在 mx 右边的每个数都判断一边是否能成为另一个峰。观察发现，在中间和左右边两端，黑色的递减序列将其连接起来了，没有拐弯，那就用 g_{i,0} 和 f2_{i} 来判断。

  3. 反转序列之后最大值需要重新找。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1e9+7;
const int N=5e5+10;
const int inf=1e9;
const int M=1005;
int f1[N],f2[N],g[N][2];
// f1[i] 表示 第i项在一个递增序列中，另一个递增序列的最小值
// f2[i] 表示 第i项在一个递减序列中，另一个递减序列的最小值

// g[i][0] 表示 第i项在一个递增序列中，另一个递减序列的最大值 
// g[i][1] 表示 第i项在一个递减序列中，另一个递增序列的最小值
int n,a[N],mx,ans;
void solve(){
    mx=0;
    for(int i=1;i<=n;i++)if(a[mx]<a[i])mx=i;
    // cout<<mx<<"\n";
    f1[0]=-inf;
    // 算左半部分的递增序列 
    for(int i=1;i<=mx;i++){
        f1[i]=inf;
        if(a[i-1]<a[i]){  // a[i-1]在 一个递增序列中 
            f1[i]=min(f1[i],f1[i-1]);
        }
        if(f1[i-1]<a[i]){ // a[i-1] 在另一个递增序列中 
            f1[i]=min(f1[i],a[i-1]);
        }
    }
    // 算右半部分的递减序列 
    f2[n+1]=inf;
    for(int i=n;i>=mx;i--){
        f2[i]=inf;
        if(a[i+1] <a[i]) f2[i]=min(f2[i],f2[i+1]);
        if(f2[i+1]<a[i]) f2[i]=min(f2[i],a[i+1]);
    }
    // a[mx] 肯定是在递减序列里的， 
    g[mx][0]=-inf ,g[mx][1]= f1[mx]; // 这样赋值是为了转移 
    for(int i=mx+1;i<=n;i++){
        g[i][0]=-inf,g[i][1]=inf; // 赋初始值 
        if(a[i-1]<a[i])g[i][0]=max(g[i][0],g[i-1][0]); // a[i-1] 属于递增序列的 
        if(a[i-1]>a[i])g[i][1]=min(g[i][1],g[i-1][1]);
        if(g[i-1][1]<a[i]) g[i][0]=max(g[i][0],a[i-1]);//a[i-1]属于递减序列的，必须合法 
        if(g[i-1][0]>a[i]) g[i][1]=min(g[i][1],a[i-1]); 
    } 

    for(int i=mx+1;i<=n;i++){
        // 当第i项属于递增序列时，检查递减序列的最大值 
        if(g[i][0] >f2[i])ans++;
    } 
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }   
    solve();
    reverse(a+1,a+1+n);
    solve();
    cout<<ans;
    return 0;
}

后记

废了一个多小时，终于写完了。

如果有什么错误或疑问还请指出。

希望分享一下做题的经验与想法，这道题不知道套路的话还是挺难想的。

如果觉得写的好要个赞不过分吧。