多状态 DP 动态规划学习笔记

AFO_Lzx · 2024-12-07 19:19:40 · 算法·理论

多状态 \texttt{DP} 学习笔记

\text{Part 0} 课前测 & 回顾一维 \texttt{DP} P10108 GESP202312 六级 闯关游戏

这题我认为用记忆化搜索比较好写，于是 5 分钟就 \texttt{AC} 了。放一个代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e4 + 5;
const int inf = INT_MIN;
int n, m, a[maxn], b[maxn];
int dp[maxn];

int dfs(int x) {
    if (x >= n) return 0;
    if (dp[x] != inf) return dp[x];

    for (int i = 0; i < m; i++) {
        dp[x] = max(dp[x], b[x] + dfs(x + a[i]));
    }

    return dp[x];
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> b[i];
        dp[i] = inf;
    }

    cout << dfs(0) << endl;
    return 0;
}

\text{Part 1} 多状态 \texttt{DP} 的入门

P1644 跳马问题

这题就是一个很简单的 \texttt{DP} 的问题，我们只需要将前面走到过的方案数量加起来就行了。不过这题数据量很小，也可以用 \texttt{DFS} 深度优先搜索回溯来做这道题。

• 确定状态：dp_{i,j} 表示走到 (j,i) 的路径总数。
• 确定答案：要求走到 (m,n) 的路径总数，所以答案应为 dp_{n,m}，倒过来即可。
• 确定状态转移方程：如下是一个方向数组，只需要用当前的坐标 (i,j) 分别加上 fx_k 和 fy_k，得到一个之前到达过的的坐标 (tx,ty)，如果这个坐标是合法的，在本题中即为是否越界，如果合法，那么：dp_{i,j} 就要加上 dp_{tx,ty} 的值。其实这题还是递推，一直累加到最后得出答案。
• 确定初始化：很简单，就是 dp_{0,0}=1，因为起点只有 1 种方案。

• 注意事项：这题在循环推状态转移方程的时候一定要把 i 和 j 交换位置！并且初始值是 i=0,j=1。

  根据上面清晰的思路，我们可以得到以下的 \texttt{AC} 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e2 + 5;
const int fx[] = {0, -2, 2, -1, 1};
const int fy[] = {0, -1, -1, -2, -2};
int n, m, dp[maxn][maxn];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    dp[0][0] = 1;
    // 初始化

    for (int j = 1; j <= m; j++) {
        for (int i = 0; i <= n; i++) {
            for (int k = 1; k <= 4; k++) {
                int tx = i + fx[k];
                int ty = j + fy[k];
                if (tx < 0 || tx > n || ty < 0 || ty > m) continue;
                // 判断越界
                dp[i][j] += dp[tx][ty];
                // 状态转移
            }
        }
    }

    cout << dp[n][m];
    return 0;
}

\text{Part 2} 小试牛刀

先来一道洛谷站外题试试手，是来自来追梦的一道题。这个 \texttt{OJ} 有点一言难尽……

\texttt{D1320【例3.4】昆虫繁殖}

这样的多状态 \texttt{DP} 具有依赖关系，比如这题，关系就是这样：

• 幼虫可以直接转变为成虫。
• 成虫可以继续繁殖更多的幼虫。

所以这题就会有 2 种不同的状态：幼虫和成虫。

随着月份的增加，整个的过程是在不断递增的，所以后面的状态不会影响前面的状态，也就是题目是无后效性的，即小问题可以拆解，就像斐波那契数列一样。直接递归的话，就会存在很多重复的情况。这个时候我们就需要用到记忆化或者递推，所以 \texttt{DP} 的本质就是空间换时间。

回归本题，我们需要开两个动态规划的数组 baby 和 dp。它们的含义如下：

所以，上面就是确定了状态，紧接着，我们就可以确定答案：dp_z。

接下来还有两个步骤，如下：

• 确定状态转移方程：

  ① baby_i=baby_{i-1}+dp_{i-x} \times y， 这就是之前的幼虫加上新产出的幼虫的数量。

  ② dp_i=dp_{i-1}+baby_{i-2}，这就是之前的成虫数量加上新长出的成虫的数量。

• 确定初始值和边界：dp_1=1,baby_1=0。这是显而易见的。

根据思路我们可以打出如下的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e2 + 5;
int baby[maxn], dp[maxn];
int x, y, z;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> x >> y >> z;
    dp[1] = 1, baby[1] = 0;

    for (int i = 2; i <= z; i++) {
        baby[i] = baby[i - 1] + dp[i - x] * y;
        dp[i] = dp[i - 1] + baby[i - 2];
    }

    cout << dp[z] << endl;
    return 0;
}

我们发现，输出的答案是 51，不对呀。为什么呢？

可以看到第一个转移方程，其中的 dp_{i-x} 目前还都是 0，所以肯定不对。

因为前 x 个月的成虫数量都是 1，所以要把 dp_1 \sim dp_x 全部设为 1。

并且 baby_i=dp_{i-x} \times y 才正确，因为第 i 个月的幼虫数量就是第 (i-x) 个月的成虫数量的 y 倍，不需要进行加减运算。

前面的代码输出的答案也是错误的，因为是 z 个月后，所以是第 (z+1) 个月，答案就是 dp_{z+1}。对应的，我们需要把循环范围改为 (x+1 \sim z+1)。

所以我们可以得到以下的 \texttt{AC} 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e2 + 5;
int baby[maxn], dp[maxn];
int x, y, z;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> x >> y >> z;
    for (int i = 1; i <= x; i++) dp[i] = 1; 

    for (int i = x + 1; i <= z + 1; i++) {
        baby[i] = dp[i - x] * y;
        dp[i] = dp[i - 1] + baby[i - 2];
    }

    cout << dp[z + 1] << endl;
    return 0;
}

\texttt{P7158 「dWoi R1」Password of Shady}

这道题我们先看看数据范围：

• Subtask 1：n=1。这里有 5 分。
• Subtask 2：n \le 6。这里有 25 分。

看来这 30 分挺好拿呀，n=1 直接输出 9，n \le 6 直接暴力枚举呀。

于是 30 分的代码就出来了，如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;

int t, n, k;
const int mod = 998244353;
const int maxn = 1e6 + 5;
bool f[maxn][10];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> t;

    while (t--) {
        cin >> n >> k;
        if (n == 1) {
            cout << 9 << "\n";
            continue;
        }
        int st = pow(10, n - 1), en = pow(10, n) - 1;

        int ans = 0;
        for (int i = st; i <= en; i++) {
            if (f[i][k] == 1) {
                ans++, ans %= mod;
                continue;
            }
            string ss = to_string(i);
            int cnt = count(ss.begin(), ss.end(), k + '0');
            if (cnt % 2 == 0) {
                f[i][k] = 1;
                ans++, ans %= mod;
            }
        }

        cout << ans << "\n";
    }

    return 0;
}

话说我的记忆化枚举怎么不行，呜呜呜，直接上 \texttt{DP}！

步骤一，确定状态：

所以这题的答案就 与 k 无关。

步骤二，确定答案：易得答案为 dp_{0,n}。

步骤三，确定状态转移方程：

步骤四，确定初始化和边界：dp_{1,1}=1,dp_{0,1}=8，因为本题考虑的是位数大于 1 的时候，不能有前导 0，也就是第一个数字不能是 0。

但是 0 可以作为一位数的答案，所以 0 需要特殊判断。

根据思路，我们可以写出如下的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5 + 5;
const int mod = 998244353;
int t, n, k, dp[2][maxn];

void init() {
    dp[0][1] = 8, dp[1][1] = 1;
    for (int i = 2; i <= maxn - 5; i++) {
        dp[0][i] = (dp[0][i - 1] * 9 + dp[1][i - 1]) % mod;
        dp[1][i] = (dp[1][i - 1] * 9 + dp[0][i - 1]) % mod;
    }

    return;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> t;
    init();

    while (t--) {
        int n, k;
        cin >> n >> k;

        if (n == 1) {
            cout << 9 << "\n";
            continue;
        }

        cout << dp[0][n] << "\n";
    }
    return 0;
}

P8395 CCC2022 S1 Good Fours and Good Fives

这题根本不需要用到 \texttt{DP}，直接暴力循环枚举即可，因为数据范围简直太小了！

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    int n;
    cin >> n;

    int f = n / 4, ans = 0;
    for (int i = 0; i <= f; i++) {
        if ((n - i * 4) % 5 == 0) ans++;
    }

    cout << ans << endl;
    return 0;
}

这不就行了嘛 \text{QAQ}。不过这节课是学 \texttt{DP}，所以不讲了……

完结……