[UOJ UNR #2]积劳成疾

时间：2023-03-08 22:25:42

来自FallDream的博客，未经允许，请勿转载，谢谢。

传送门

区间最大值的题emmmm

想到构建笛卡尔树，这样自然就想到了一种dp

f[i][j]表示大小为i的笛卡尔树，根的权值是j的答案。

转移的时候枚举左右子树的大小，对权值那一维前缀和转移。

然后在每次转移的时候，把已经可以确定最大值的段的贡献乘进去就可以了。

#include<iostream>

#include<cstdio>

#define MN 400

#define mod 998244353

using namespace std;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int w[MN+],f[MN+][MN+],n,K,pw[MN+][MN+];

int main()

{

    n=read();K=read();f[][]=;

    for(int i=;i<=n;++i) w[i]=read(),f[][i]=,pw[i][]=;

    for(int i=;i<=n;++i) for(int j=;j<=n;++j) pw[i][j]=1LL*pw[i][j-]*w[i]%mod;

    for(int i=;i<=n;++i)

    {

        for(int k=;k<=n;++k)

            for(int j=;j<i;++j)

            {

                int res=1LL*f[j][k]*f[i--j][k-]%mod;

                if(i>=K) res=1LL*res*pw[k][max(,min(,i-j--K+)-max(-K+,-j)+)]%mod;

                f[i][k]=(f[i][k]+res)%mod;

            }

        for(int k=;k<=n;++k) f[i][k]=(f[i][k]+f[i][k-])%mod;

    }

    printf("%d\n",f[n][n]);

    return ;

}

相关文章