P4590:「TJOI2018」游园会 – 题解

DP 套 DP

总有一种之前纪中 A 组做过的感觉，没想到真的做过，只是那个时候并不知道这个东西叫做 DP 套 DP。

如果不考虑匹配到第 \(i\) 位、只考虑防止出现 \(NOI\) 字串那可以直接 \(dp[i][j]\) 进行匹配并计数。这个很简单。主要是如何刻画子序列匹配的状态。类似的字符串题可以考虑在自动机上做，然而我们并没有这样的自动机。我们考虑用 DP 套 DP。

怎样 DP 套 DP 呢？我们想一下匹配最长子序列的过程：

\[ dp[i][j] = \max \begin{cases} dp[i – 1][j] \\ dp[i][j – 1] \\ dp[i – 1][j – 1] + 1, (S_i = T_j) \end{cases} \]

如果我们能把这个东西塞进去就好了。首先这两个 DP 的 \(i\) 是可以共用的，而且我们需要刻画的也仅限于这个 \(i\)，这个就很好。设 \(dp[i][j][STAT]\) 为计算了前 \(i\) 位、与 \(NOI\) 匹配到第 \(j\) 位且与串匹配成 \(STAT\)。这个 \(STAT\) 记录 \(T\) 串中哪些位置被匹配了。（这个可以用额外的 DP 来算出来那些匹配位置）。

代码

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

using namespace std;

const int MAX_N = 1010, MAX_M = 15, mod = 1e9 + 7;
const int nxt_len[3][3] = {{1, 0, 0}, {1, 2, 0}, {1, 0, 3}};

int n, m, dp[2][1 << MAX_M][3], trans[1 << MAX_M][3], f[2][MAX_N], org[MAX_N], ans[MAX_N];
char str[MAX_N];

void build()
{
    for (int stat = 0; stat < (1 << m); stat++)
    {
        for (int i = 0; i < m; i++)
            f[0][i + 1] = f[0][i] + ((stat >> i) & 1);
        for (int i = 0; i < 3; i++)
        {
            // get the new stat after choosing char i;
            for (int j = 1; j <= m; j++)
            {
                f[1][j] = max(f[1][j - 1], f[0][j]);
                if (i == org[j])
                    f[1][j] = max(f[1][j], f[0][j - 1] + 1);
            }
            int nxt = 0;
            for (int j = 1; j <= m; j++)
                nxt |= (f[1][j] - f[1][j - 1]) << (j - 1);
            trans[stat][i] = nxt;
        }
    }
}

int main()
{
    scanf("%d%d%s", &n, &m, str + 1);
    for (int i = 1; i <= m; i++)
        org[i] = (str[i] == 'N' ? 0 : (str[i] == 'O' ? 1 : 2));
    build(), dp[0][0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        memset(dp[i & 1], 0, sizeof(dp[i & 1]));
        for (int j = 0; j < (1 << m); j++)
            for (int len = 0; len < 3; len++)
                for (int c = 0; c < 3; c++)
                    if (!(len == 2 && c == 2))
                        dp[i & 1][trans[j][c]][nxt_len[len][c]] = (0LL + dp[i & 1][trans[j][c]][nxt_len[len][c]] + dp[!(i & 1)][j][len]) % mod;
    }
    for (int stat = 0; stat < (1 << m); stat++)
        for (int len = 0; len < 3; len++)
            ans[__builtin_popcount(stat)] = (0LL + ans[__builtin_popcount(stat)] + dp[n & 1][stat][len]) % mod;
    for (int i = 0; i <= m; i++)
        printf("%d\n", ans[i]);
    return 0;
}