【2019多校第一场补题 / HDU6578】2019多校第一场A题1001Blank——dp

HDU6578链接

题意

有一串字符串，仅由 ${0, 1, 2, 3}$ 组成，长度为 $n$，同时满足 $m$ 个条件。每个条件由三个整数组成：$l、r、x$ 表示在这个字符串的 $[l, r]$ 这个区间内，有且仅有 $x$ 个不同的字符，求问可能的组合有多少种（mod 998244353）

分析题意

因为前几天刚刚写了牛客暑期多校第二场，其中有一道题：ABBA（我的题解）感觉有点接近，所以第一想法就是dp了。但是这道题的字符多，不能像ABBA一样压缩至一维。所以只能想想看当时牛客官方给的题解的方法了。
考虑到之后需要判断条件是否满足，所以我第一感觉就是得定义一个超多维度的dp数组：

const int MAXN = 110;
long long dp[MAXN][MAXN][MAXN][MAXN][MAXN];

各个维度的定义如下：

对于 dp[a][b][c][d][t]
表示整个字符串长度为 t ，最后一次出现 0 的位置为 a，最后一次出现 1 的位置为 b ，最后一次出现 2 的位置为 c ，最后一次出现 3 的位置为d

然后可以得到状态转移方程

dp[t + 1][b][c][d][t + 1] += dp[a][b][c][d][t];
dp[a][t + 1][c][d][t + 1] += dp[a][b][c][d][t];
dp[a][b][t + 1][d][t + 1] += dp[a][b][c][d][t];
dp[a][b][c][t + 1][t + 1] += dp[a][b][c][d][t];

当然这个数组肯定是没法开的，所以把 t 压缩了，变成滚动dp

const int MAXN = 110;
long long dp[MAXN][MAXN][MAXN][MAXN][2];

然后通过滚动的方式来实现。
但是这并不是卡死这种方法的原因。
根据上面这些，可以写出整个dp过程，大概就是这样：

for (int t = 1; t <= n; t++) {
    for (int a = 0; a <= t; a++)
        for (int b = 0; b <= t; b++)
            for (int c = 0; c <= t; c++)
                for (int d = 0; d <= t; d++)
                    dp[a][b][c][d][t & 1] = 0;
    for (int a = 0; a <= t; a++)
        for (int b = 0; b <= t; b++)
            for (int c = 0; c <= t; c++)
                for (int d = 0; d <= t; d++) {
                    dp[t + 1][b][c][d][t & 1] += dp[a][b][c][d][t ^ 1];
                    dp[a][t + 1][c][d][t & 1] += dp[a][b][c][d][t ^ 1];
                    dp[a][b][t + 1][d][t & 1] += dp[a][b][c][d][t ^ 1];
                    dp[a][b][c][t + 1][t & 1] += dp[a][b][c][d][t ^ 1];
                }
}

这个复杂的……这还没加上判断是否满足条件……
无论是时间是还是空间上，估计都悬（时间上应该是一定过不了了）
然后只能继续压缩。
考虑到最后无论哪种状态下，$a, b, c, d$ 四个变量中，必定有一个且仅有一个变量的值为 t 。而且在这道题中，字符 ${0, 1, 2, 3}$ 完全等价。所以我们再压缩一维

const int MAXN = 110;
long long dp[MAXN][MAXN][MAXN][2];

此时的意义如下：

对于变量 dp[x][y][z]
表示字符 ${0, 1, 2, 3}$ 中，其中一个最后出现的位置为当前的字符最后（由于这个条件恒成立，所以并未被记录在数组中），剩下的三个字符分别出现在$x, y, z$处，且保证 $i < x \leq y \leq z (i 为当前字符长度)$ （仅当 $x = y = 0$ 时满足前面一个等于号，后面的等于号同理。而字符串长度至少为1，且此时$x、y、z$均为0，所以不存在 $i = x$ 的情况。）而后面的长度为 2 的维度指代当前状态和 上一个状态（滚动dp）

可以得到状态转移方程：

// i 为当前字符串长度，cur 为当前状态，last 为上一个状态
dp[x][y][z][cur] += dp[x][y][z][last];					// 加入的字符与上一个加入的字符相同
dp[i - 1][y][z][cur] += dp[x][y][z][last];
dp[i - 1][x][z][cur] += dp[x][y][z][last];
dp[i - 1][x][y][cur] += dp[x][y][z][last];

得到整个 dp 过程：

dp[0][0][0][0] = 1;
int cur = 1;
int last = 0;
for (int i = 1; i <= n; i++)
    for (int x = 0; x <= i; x++)
        for (int y = 0; y <= x; y++)
            for (int z = 0; z <= y; z++)
                dp[x][y][z][cur] = 0;
for (int x = 0; x < i; x++)
    for (int y = 0; y <= x; y++)
        for (int z = 0; z <= y; z++) {
            dp[x][y][z][cur] += dp[x][y][z][last];
            dp[i - 1][y][z][cur] += dp[x][y][z][last];
            dp[i - 1][x][z][cur] += dp[x][y][z][last];
            dp[i - 1][x][y][cur] += dp[x][y][z][last];

            dp[x][y][z][cur] %= mod;                        // 别忘了 mod
            dp[i - 1][y][z][cur] %= mod;
            dp[i - 1][x][z][cur] %= mod;
            dp[i - 1][x][y][cur] %= mod;
        }
swap(cur, last);

考虑条件
需要判断一个区间内是否满足有多个不同的字符
我们可以根据区间右端为基准，当前dp的字符串长度到达一个条件的右端的时候，通过 $x、y、z$ 的值来判断是否到达了要求，如果没有则将此 dp 的赋值为0。如果懒得思考可以直接分类讨论一下就行了。虽然代码会比较长。

AC代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 110;
const int mod = 998244353;

long long dp[MAXN][MAXN][MAXN][2];
// dp[i][j][k] 表示上一次出现不同数字的位置分别是 i、j、k、当前位置

struct Conditions {
    int l, x;

    Conditions(int ll, int xx) : l(ll), x(xx) {}
};

vector <Conditions> conditions[MAXN];    // 用来保存要求

int main() {
#ifdef ACM_LOCAL
    freopen("./in.txt", "r", stdin);
    freopen("./out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int a, b, c;
        for (int i = 0; i < MAXN; i++) {
            conditions[i].clear();
        }
        for (int i = 0; i < m; i++) {
            cin >> a >> b >> c;
            conditions[b].push_back(Conditions(a, c));        // 要求按照 r 的不同来保存
        }
        dp[0][0][0][0] = 1;
        int cur = 1;
        int last = 0;
        for (int i = 1; i <= n; i++) {
            for (int x = 0; x <= i; x++) {
                for (int y = 0; y <= x; y++) {
                    for (int z = 0; z <= y; z++) {
                        dp[x][y][z][cur] = 0;
                    }
                }
            }
            for (int x = 0; x < i; x++) {
                for (int y = 0; y <= x; y++) {
                    for (int z = 0; z <= y; z++) {
                        dp[x][y][z][cur] += dp[x][y][z][last];
                        dp[i - 1][y][z][cur] += dp[x][y][z][last];
                        dp[i - 1][x][z][cur] += dp[x][y][z][last];
                        dp[i - 1][x][y][cur] += dp[x][y][z][last];

                        dp[x][y][z][cur] %= mod;
                        dp[i - 1][y][z][cur] %= mod;
                        dp[i - 1][x][z][cur] %= mod;
                        dp[i - 1][x][y][cur] %= mod;
                    }
                }
            }
            for (int s = 0; s < conditions[i].size(); s++) {
                for (int x = 0; x < i; x++) {
                    for (int y = 0; y <= x; y++) {
                        for (int z = 0; z <= y; z++) {
                            int cnt = 1 + (x >= conditions[i][s].l ? 1 : 0) + (y >= conditions[i][s].l ? 1 : 0) +
                                      (z >= conditions[i][s].l ? 1 : 0);    // 判断剩下三个位置是否满足条件
                            if (cnt != conditions[i][s].x)
                                dp[x][y][z][cur] = 0;
                        }
                    }
                }
            }
            swap(cur, last);
        }
        long long ans = 0;                        // 求算最终答案。需要把所有的情况都加起来
        for (int x = 0; x < n; x++) {
            for (int y = 0; y <= x; y++) {
                for (int z = 0; z <= y; z++) {
                    ans += dp[x][y][z][last];
                    ans %= mod;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}