Description

题目链接

题目大意：给定 $n, m$，要求找出长度为 $n$，每个元素都在 $[1, m]$，且最长上升子序列的长度为 $3$ 的序列个数。$1 \le n \le 1000, 1 \le m \le 10$。

Solution

AtCoder 的 DP 一般都难在状态的设计，求转移方程的难度就相比之下不是那么大。

注意到 $m$ 很小，在设计状态时应该多加利用。

在经典的最长上升子序列问题的 $O(n \log n)$ 解法中，我们记录的 $f_i$ 是长度为 $i$ 的最长上升子序列的末尾元素的最小值。

类似的状态可以被用来解决这道题。设 $f(i, a, b, c)$ 表示考虑了前 $i$ 位，长度为 $1, 2, 3$ 的最长上升子序列中结尾的最小值为 $a, b, c$ 的个数。

然后只需要枚举 $x \in [1, m]$，看它对长度为几的最长上升子序列有贡献即可。

时间复杂度 $O(nm^4)$。

Code

#include <bits/stdc++.h>

template <class T>
inline void read(T &x) {
    x = 0;
    int f = 0;
    char ch = getchar();
    while (!isdigit(ch))    { f |= ch == '-'; ch = getchar(); }
    while (isdigit(ch))     { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
    x = f ? -x : x;
    return ;
}

typedef unsigned long long uLL;
typedef long long LL;

const LL mod = 998244353;

LL f[1010][12][12][12];
LL ans;
int n, m;

int main() {
    read(n), read(m);
    f[0][m + 1][m + 1][m + 1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int a = 1; a <= m + 1; ++a) {
            for (int b = a; b <= m + 1; ++b) {
                for (int c = b; c <= m + 1; ++c) {
                    for (int x = 1; x <= std::min(a, m); ++x)    f[i][x][b][c] += f[i - 1][a][b][c], f[i][x][b][c] %= mod;
                    for (int x = a + 1; x <= std::min(b, m); ++x)    f[i][a][x][c] += f[i - 1][a][b][c], f[i][b][x][c] %= mod;
                    for (int x = b + 1; x <= std::min(c, m); ++x)    f[i][a][b][x] += f[i - 1][a][b][c], f[i][a][b][x] %= mod;
                }
            }
        }
    }
    for (int i = 1; i <= m; ++i) {
        for (int j = i + 1; j <= m; ++j) {
            for (int k = j + 1; k <= m; ++k) {
                ans += f[n][i][j][k], ans %= mod;
            }
        }
    }
    printf("%lld\n", ans);
    return 0;
}