「Universal OJ」#311:「UNR #2」积劳成疾 – 题解

主要思路

这个处理方式很妙啊。根据 yyb 的博客介绍，这种处理方式被称作是「最大值分治」。

我们可以考虑设计状态 \(dp[i][j]\) 为长度为 \(i\)、最大值不超过 \(j\) 的方案数。那么，我们可以枚举一个 \(k\) 作为 \(j\) 的位置，然后强制这个 \(k\) 在这一段里面是最右边的 \(j\)，具体写出转移就是：

\[ dp[i][j] = dp[i][j – 1] + \sum_{k = 1}^i dp[k – 1][j] \times dp[i – k][j – 1] \times w^c \]

注意右侧的 \(dp[i – k][j – 1]\)，可以保证该位置为最右侧的 \(j\)，这样就不会算重复了。其中 \(c\) 是当前序列里包含这个数的区间个数，画个图，算最右和最左的区间左边缘之差即可。

代码

// UOJ311.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 440, mod = 998244353;

int n, m, wi[MAX_N][MAX_N], dp[MAX_N][MAX_N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &wi[1][i]), wi[0][i] = 1;
        for (int j = 2; j <= m; j++)
            wi[j][i] = 1LL * wi[j - 1][i] * wi[1][i] % mod;
    }
    for (int i = 0; i <= n; i++)
        dp[0][i] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i][j - 1];
            for (int k = 1; k <= i; k++)
            {
                int tmp = 1LL * dp[k - 1][j] * dp[i - k][j - 1] % mod;
                int idx = max(0, min(k, i - m + 1) - max(1, k - m + 1) + 1);
                // int idx = min({m, max(0, i - m + 1), k, i - k + 1});
                tmp = 1LL * tmp * wi[idx][j] % mod;
                dp[i][j] = (0LL + dp[i][j] + tmp) % mod;
            }
        }
    printf("%d\n", dp[n][n]);
    return 0;
}