Link

CF1914 D Array Collapse

Question

初始给出一个数组 \(\{P\}\) ，数组中每个值都不相同，我们可以选中 \(P\) 数组中连续的一段，然后删除除了最小值以外的所有元素，求删除多次（包括 \(0\) 次）后，剩下的数组的数量

Solution

当时就没怎么往 DP 方面想，没想到还能这样 DP

定义 \(F[i]\) 表示以 \(i\) 为结尾的数量，但是注意如果枚举到 \(j>i\) ，\(F[i]\) 很可能没定义

具体地，如果枚举到一个 \(j>i\) 有 \(a[j]<a[i]\) 那么在枚举到 \(j\) 时 \(F[i]\) 也就没有定义了，因为不可能以 \(a[i]\) 结尾

考虑到不可能以 \(a[i]\) 结尾，但是我们能替换 \(a[i]\) 和 \(a[j]\) 的值来帮我们转移方程

具体地，如果 \(a[i]>a[j]\) ，且 \(i<k<j\) 的每个 \(a[k]>a[j]\) 那么我们就可以用一次删除 \([i,j]\) 的操作，把最后一个字母从 \(a[i]\) 替换成 \(a[j]\)

所以对于每一个 \(j\) ，我们都可以找到左边第一个小于 \(a[j]\) 的 \(a[i]\) ，有三种选择

• 加在后面
• 要么替换 \((i,j)\) 中的最后一个字母，也就是加上 \(\sum\limits_{k=i+1}^{j-1} F[k]\)
• 删除 \([i+1,j)\) 就相当于加上 \(i\) 之前的，有定义的 \(F[i]\) 的值

这种定义和转移还是第一次见，方程刷到后面会发现前面的有些 \(F[i]\) 没有定义

具体实现利用单调栈，维护左边第一个比他小的数

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int TT=998244353;
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

void solve(){
    int n=read();
    vector<int> a(n+1,0),F(n+1,0),sum(n+1,0);
    stack<int> st;
    for(int i=1;i<=n;i++) a[i]=read();
    int ans=0;
    for(int i=1;i<=n;i++){
        while(!st.empty()&&a[i]<a[st.top()]) ans=(ans-F[st.top()])%TT,st.pop();
        if(st.empty()) F[i]=(sum[i-1]+1)%TT;
        else F[i]=(sum[i-1]-sum[st.top()]+ans)%TT;
        sum[i]=(sum[i-1]+F[i])%TT;
        ans=(ans+F[i])%TT;
        st.push(i);
    }
    printf("%lld\n",(ans+TT)%TT);
}

signed main(){
    freopen("D.in","r",stdin);
    int T=read();
    while(T--) solve();
    return 0;
}