浅谈棋盘类 DP

棋盘 DP 是为了做什么？

棋盘 DP 通常是：在一个 $n \times m$ 的网格上，从起点走到终点（或覆盖某些格子），每走一步会产生 收益 / 代价 / 可行性变化 ，要：

• 求 最小代价 / 最大收益
• 求 方案数
• 判断 是否存在
• 输出一条 具体路径（还原）
• 走法可能变成 两个人同时走 、恰好走 $k$ 步 、带障碍 、带取模 / 字典序构造 等 \

核心目标是：把 走到某个格子时的历史信息 压缩成一个状态。

三要素!!

状态怎么定义：

常见的基本状态就是：$dp_{i, j}$ 表示走到格子 $(i,j)$ 时的 最优值 / 方案数 / 可行性 。

如果问题更复杂，就添加维度：

$dp_{i, j, t}$：走到 $(i,j)$ 且已经走了 $t$ 步
$dp_{i, j, r}$：走到 $(i,j)$ 且某个量的余数为 $r$
$dp_{s, i, j}$：状态压缩（例如某一行的占用情况）

基本上就是：状态 = 位置 + 未来还需要知道的最少信息 。

转移方程怎么写：

棋盘最常见移动是 右 / 下 （也可能 四方向 、 八方向 、 骑士跳 等）。用移动表 $dx, dy$ 表示即可。

例如只允许 右 / 下 ：

$$dp_{i, j} \leftarrow \min(dp_{i - 1, j}, dp_{i, j - 1}) + w_{i, j} $$

或者求 $\max$ ，这种属于最优类型。

对于计数类型可表示为：

$$dp_{i, j} \leftarrow dp_{i - 1, j} + dp_{i, j - 1} $$

遍历顺序与边界：

只要转移依赖的是 已经算过的状态 ，顺序就对。

只依赖 上 / 左 ：按行 从上到下 、按列 从左到右
依赖 下 / 右 ：反向遍历
四方向但无环：按 拓扑序 （例如按距离层数）
有环：一般要换成最短路 / 最长路（DAG）或 DP + 松弛思维

对于边界处理常用：

设定不可达为 $+\infty$（最小化）或 $-\infty$（最大化）
单独初始化起点 $dp_{1, 1}$

常见棋盘 DP 题型!!（大致分类）

1、单人单调路径最值（只能右 / 下）

适用于求 最大/最小路径和、最短代价 ，同时 障碍不可走 的情况。
常用的状态表示为：$dp_{i, j}$ 表示到达 $(i,j)$ 的最优值。
状态转移为：$dp_{i, j} = \min(dp_{i - 1, j}, dp_{i, j - 1}) + w_{i, j}$ 或者将 $\min$ 替换为 $\max$ 。
时间复杂度为 $O(n, m)$ 。
不可达用 $+\infty/-\infty$ ，起点/终点是障碍直接无解。

2、单人单调路径计数（右 / 下，取模）

和 最值 类似，只是这里需要计数，因为计数都比较大，必然需要 取模 。
常用的状态表示为：$dp_{i, j}$ 表示到 $(i,j)$ 的路径条数。
状态转移为：$dp_{i, j} = (dp_{i - 1, j} + dp_{i, j - 1}) \mod MOD$ 。
时间复杂度为 $O(n, m)$ 。
不可达用 $0$ 。

3、四方向网格最值（可上 / 下 / 左 / 右，但步数有限）

适用于恰好走 $k$ 步 最小 / 最大，回到原点 / 到某点 。
常用的状态表示为：$dp_{t, i, j}$ 表示走了 $t$ 步到 $(i,j)$ 的最优值。
状态转移为：$dp_{t, i, j}=\min_{\text{邻居 }(x,y)} \big(dp_{t - 1, x, y}+cost(x,y\to i,j)\big)$ 。
时间复杂度为 $O(knm)$（常可滚动数组降空间）。
需要注意 $k$ 大会爆，需要观察 / 优化 。

4、带额外维度的路径 DP（余数 / 血量 / 次数 / 颜色）

适用于 路径和要满足 $\bmod M$ 条件 ，经过特殊格子次数有限 ，状态要 携带某个属性 。
常用的状态表示为：$dp_{i, j, s}$ 表示到 $(i,j)$ 且属性为 $s$ 的最优 / 计数 。
状态转移为：$dp_{i,j,s'} \leftarrow dp_{i-1,j,s} \text{ 或 } dp_{i,j-1,s}$ ，其中 $s'!=f(s,w_{i, j})$ 。
时间复杂度为 $O(nm\cdot |S|)$ 。
需要注意 $|S|$ 过大要压缩（集合去重、只保留有效状态等）

5、字典序最小路径构造（DP + 分层贪心 / BFS）

适用于 输出最小字典序路径字符串 ，允许修改若干格子 / 代价约束下最小字典序 。
可以先 DP 求 最早能到达的层 / 最远能做到的条件，再 按层扫描 下一步可达集合，用最小字符扩展。
需要注意 能到达 集合要去重（用 visited / bitset）

6、两个人同步走（两条路径并行）

适用于 两条从 $(1,1)$ 到 $(n,n)$ 的路径，最大化总收益 ，并且 重叠格子只算一次 。
状态（经典降维）表示为：令步数 $t$ 同步，则 $i+j=t+2$ ，$dp_{t,i_1,i_2}$ 或滚动成 $dp_{i_1,i_2}$ ，列坐标：$j_1=t+2-i_1,\ j_2=t+2-i_2$ 。
状态转移：两人本步各来自上 / 左，共 $4$ 组合 。
时间复杂度 $O(n^3)$ 。
需要注意两人同格时只能加一次权值，下标合法性（$j$ 要在 $[1,n]$）

7、四角四向预处理（四个 dp 表拼答案）

适用于 两条路径不交叉 / 两人从不同角走到中间 。
状态表示为 $4$ 个表：1、$dp1$：从左上到 $(i,j)$ 最优，2、$dp2$：从右下到 $(i,j)$ 最优，3、$dp3$：从右上到 $(i,j)$ 最优，4、$dp4$：从左下到 $(i,j)$ 最优，再枚举交汇点，按两种交叉方式取最大。
时间复杂度为：预处理 $4 \times O(nm)$，枚举 $O(nm)$ 。
需要注意 交汇点不能在边界 （要留出 拐弯 空间），两种交叉方式都要算，少算会 WA

8、子矩形计数 / 最大矩形（高度 DP + 栈）

适用于 统计全 $0$ 子矩形个数 ，求最大全 $1$ 矩形面积 。
可以先算高度 $h_{i, j}$：连续 $0/1$ 的 向上高度 ，每行当作柱状图，用 单调栈 或 DP 统计 。
时间复杂度为 $O(nm)$ 。
需要注意 栈里维护的是高度单调性，计数题要注意 以 $j$ 为右端 的累积 DP 写法

9、矩形切分 DP（Chocolate Bar 类）

适用于 把 $a\times b$ 切成若干块，最小代价 / 最少浪费，允许横切或竖切。
状态表示为：$dp_{a, b}$ 表示尺寸为 $a\times b$ 的最优。
状态转移：横切的时候 $dp_{a, b}=\min_{k< a}{dp_{k, b}+dp_{a - k, b}}$ ，竖切同理 。
时间复杂度为 通常 $O(A^2B + AB^2)$（需要看范围）。
注意对称性：$dp_{a, b}=dp_{b, a}$ 可减半 。

10、棋盘覆盖 / 操作最少（状态压缩 DP）

适用于 $1×m$ 或 $n×m$ 小 $n$（如 $n≤10 \sim 15$），多米诺铺砖、覆盖障碍、$2×2$ 操作等 。
状态表示为：$dp_{col,mask}$：处理到某列，当前列的占用状态为 $mask$ 。
枚举如何在这一列放置并影响下一列 $mask$ 。
时间复杂度为 $O(m \cdot 2^n \cdot \text{转移系数})$ 。

题型例题讲解

1、单人单调路径最值（只能右 / 下）

题目描述

给定由非负整数组成的 $n \times n$ 的正方形矩阵，需要寻找一条路径：

• 以左上角为起点。
• 每次只能向右或向下走。
• 以右下角为终点。
• 如果我们把沿路遇到的数进行相乘，积应当以尽可能少的 $0$ 结尾。

输入格式

第一行包含一个整数 $n (2 \leq n \leq 1000)$，$n$ 为矩阵的规模，接下来的 $n$ 行包含矩阵的元素（不超过 $10^9$ 的非负整数）。

输出格式

第一行应包含结尾最少的 $0$ 的个数，第二行打印出相应的路径（译注：D 为下，R 为右）。

输入输出样例 #1

输入 #1

3
1 2 3
4 5 6
7 8 9

输出 #1

0
DDRR

解题思路

重点关注

这个问题的关注点明显就是数字末尾 $0$ 的数量，一个整数末尾 $0$ 的个数 $=$ 它能被 $10=2\cdot 5$ 整除多少次，也就是质因子分解里：

$$\text{zeros} = \min(\#2,\#5)$$

路径乘积的质因子个数等于路径上每个格子该质因子个数的和。

于是对每个格子值 $a_{i,j}$ 定义：

• $c2_{i, j} = v_2(a_{i,j})$（$2$ 的指数）

• $c5_{i, j} = v_5(a_{i,j})$（$5$ 的指数）

若路径为 $P$，则

$$S2(P)=\sum_{(i,j)\in P} c2_{i, j},\quad S5(P)=\sum_{(i,j)\in P} c5_{i, j} $$$$\text{zeros}(P)=\min(S2(P),S5(P))$$

这时候只要分别最小化 $S2$ 和 $S5$ 就够了

令

$$A=\min_{P} S2(P),\quad B=\min_{P} S5(P)$$

则最优答案

$$\text{OPT}=\min_{P}\min(S2(P),S5(P)) = \min(A,B) $$

证明：

• 对任意路径 $P$，有 $S2(P)\ge A,\ S5(P)\ge B$，所以

  $$\min(S2(P),S5(P)) \ge \min(A,B)$$

  因此 $\text{OPT}\ge \min(A,B)$。

• 取达到 $A$ 的路径 $P_2$，则

  $$\min(S2(P_2),S5(P_2)) \le S2(P_2)=A$$

  同理达到 $B$ 的路径 $P_5$ 给出 $\text{OPT}\le B$。于是 $\text{OPT}\le \min(A,B)$。

上下界相同，结论成立。

所以：做两次普通网格 DP：一次最小化 $2$ 的指数和，一次最小化 $5$ 的指数和，最后取终点更小的那个。

$0$ 的特殊情况

矩阵元素允许为 $0$ 。 如果路径经过 $0$ ，则乘积为 $0$ ，而十进制表示的 $0$ 末尾 $0$ 的个数是 $1$ （只有一个字符 $0$）。

因此：

• 若正常 DP 得到的最优答案已经是 $0$ 或 $1$ ，那一定不需要走 $0$（或走不走都一样）。

• 若正常 DP 的最优答案 大于 $1$ ，并且矩阵中存在某个 $0$，那么走过这个 $0$ 就能把答案降到 $1$ ，应当输出经过 $0$ 的一条路径。

实现技巧：DP 时把值为 $0$ 的格子的 $c2,c5$ 设成很大的 $inf$ ，让 DP 尽量不走 $0$ ；另外记录任意一个 $0$ 的坐标 $(zx,zy)$ 备用。

整理

状态表达

• $dp2_{i, j}$：从 $(1,1)$ 到 $(i,j)$ 路径上 $c2$ 之和的最小值

• $dp5_{i, j}$：同理，对 $c5$

• $par2_{i, j} / par5_{i, j}$：记录从上来还是从左来，用于还原路径

转移（标准右/下网格）

$$dp2_{i, j}=c2_{i, j}+\min(dp2_{i - 1, j},dp2_{i, j - 1}) $$$$dp5_{i, j}=c5_{i, j}+\min(dp5_{i - 1, j},dp5_{i, j - 1}) $$

时间复杂度

$O(n^2)$ 时间，$O(n^2)$ 空间（$n\le 1000$）。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, c2[N][N], c5[N][N], dp2[N][N], dp5[N][N], zx = -1, zy = -1;
char par2[N][N], par5[N][N];
int f(int x, int p) {
    int r = 0;
    while (x % p == 0) {
        x /= p;
        r++;
    }
    return r;
}
string path(char par[N][N]) {
    string s;
    int i = n, j = n;
    while (!(i == 1 && j == 1)) {
        char f = par[i][j];
        if (f == 'D') {
            s.push_back('D');
            i--;
        } else {
            s.push_back('R');
            j--;
        }
    }
    reverse(s.begin(), s.end());
    return s;
}
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1, x; j <= n; j++) {
            cin >> x;
            if (x == 0) {
                zx = i, zy = j;
                c2[i][j] = c5[i][j] = inf;
            } else {
                c2[i][j] = f(x, 2);
                c5[i][j] = f(x, 5);
            }
        }
    }
    for (int i = 0; i <= n; i++) dp2[i][0] = dp5[i][0] = dp2[0][i] = dp5[0][i] = inf;
    dp2[1][1] = c2[1][1];
    dp5[1][1] = c5[1][1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == 1 && j == 1) continue;
            if (dp2[i - 1][j] < dp2[i][j - 1]) {
                dp2[i][j] = dp2[i - 1][j] + c2[i][j];
                par2[i][j] = 'D';
            } else {
                dp2[i][j] = dp2[i][j - 1] + c2[i][j];
                par2[i][j] = 'R';
            }
            if (dp5[i - 1][j] < dp5[i][j - 1]) {
                dp5[i][j] = dp5[i - 1][j] + c5[i][j];
                par5[i][j] = 'D';
            } else {
                dp5[i][j] = dp5[i][j - 1] + c5[i][j];
                par5[i][j] = 'R';
            }
        }
    }
    int bt2 = dp2[n][n];
    int bt5 = dp5[n][n];
    int bt = min(bt2, bt5);
    if (zx != -1 && zy != -1 && bt > 1) {
        cout << 1 << "\n";
        string s;
        s.append(zx - 1, 'D');
        s.append(zy - 1, 'R');
        s.append(n - zx, 'D');
        s.append(n - zy, 'R');
        cout << s << "\n";
        return;
    }
    if (bt2 <= bt5) {
        cout << bt2 << "\n";
        cout << path(par2) << "\n";
    } else {
        cout << bt5 << "\n";
        cout << path(par5) << "\n";
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

2、单人单调路径计数（右 / 下，取模）

题目描述

国际象棋棋盘最底行站了一个兵。 它只有两种行动方式： 向左上或向右上走。 它可以选择从最低行哪个节点开始他的旅程。

每个格子上有 $0\sim9$ 颗豌豆，而士兵想移动到最上一行并且积累到尽可能多的豌豆。同时，因为这个士兵必须把豌豆平均分给自己和他的 $k$ 个兄弟，他所收集到的豌豆必须是 $k+1$ 的倍数。请找到他可以收集到的最多豌豆，并确定他的操作序列。

规定士兵不能扔掉豌豆，并且他必须捡起所到达的每一个格子的所有豌豆。

输入格式

第一行三个整数 $n,m,k(2 \le n,m \le 100, 0 \le k \le 10)$ 行数、列数、士兵的兄弟们。

接下来一个 $n \times m$ 的矩阵，每个元素均是 $0\sim9$ 的整数（不空格），描述该格的豌豆。第一行是最上一行，最后一行是最下一行。

输出格式

如果不能收集到 $k+1$ 倍数的豌豆，输出 -1.

否则，输出第一行一个整数，为最多豌豆数；第二行一个整数，为士兵开始移动的位置；第三行包括 $n-1$ 个字母，L（表示向左上走）或 R（表示向右上走），表示士兵的行动序列。

如果有多种收集到相同且是 $k+1$ 倍数数量的豌豆，你可以任意输出一种方案。

输入输出样例 #1

输入 #1

3 3 1
123
456
789

输出 #1

16
2
RL

输入输出样例 #2

输入 #2

3 3 0
123
456
789

输出 #2

17
3
LR

输入输出样例 #3

输入 #3

2 2 10
98
75

输出 #3

-1

解题思路

这个题目并不是纯纯计数，重点讲一下状态的表达，如果不考虑能不能被 $k + 1$ 整除的情况，很明显就是一个简单的棋盘 DP 最值问题，加上整除的情况就需要做一下 模约束 了。

很明显可以看到 $0 \le k \le 10$ ，非常小，$k + 1 = 11$ 。

状态表示

$dp_{i, j, r}$ 表示从 底行 走到格子 $(i,j)$（一路向上），收集到的最大豆子数，且该总和 $\mod K = r$ 。

初始化（起点在底行任意列）：$dp_{n, j, {a_{n, j} \bmod K}} = a_{n, j}$ 。

不可达用 $-inf$ 。

转移

很明显，从下往上推，要到达 $(i,j)$（上面一行），它只能从下一行的两格来：

• 从 $(i+1, j-1)$ 来：这是一次 向上右 R
• 从 $(i+1, j+1)$ 来：这是一次 向上左 L

设当前格子的值为 $v = a_{i, j}$，如果前驱状态余数为 $rp$，那么新余数：$nr = (rp + v) \mod K$ 。

更新最大值：

$$dp_{i, j, nr} = \max(dp_{i, j, nr}, dp_{i + 1, pj, rp} + v) $$

同时记录父指针用于还原路径：父列 $pj$ 、父余数 $rp$ 、以及该步是 L/R 。

最终输出：在顶行 $i=1$ 中找最大 $dp_{1, j, 0}$（余数必须为 $0$）。若都不可达输出 $-1$ 。

对于路径还原可以参考上面的程序。

时间复杂度：$O(nmk)$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e2 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, k, dp[N][N][15], parj[N][N][15], parr[N][N][15], a[N][N];
char mv[N][N][15];
inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c; cin >> c;
            a[i][j] = c - '0';
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int r = 0; r < k + 1; r++) {
        dp[i][j][r] = -inf;
        parj[i][j][r] = parr[i][j][r] = -1;
    }
    for (int j = 1; j <= m; j++) {
        int r = a[n][j] % (k + 1);
        dp[n][j][r] = a[n][j];
    }
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            int v = a[i][j];
            if (j - 1 >= 1) {
                int pj = j - 1;
                for (int rp = 0; rp < k + 1; rp++) if (dp[i + 1][pj][rp] > -inf) {
                    int nr = (rp + v) % (k + 1);
                    int vl = dp[i + 1][pj][rp] + v;
                    if (vl > dp[i][j][nr]) {
                        dp[i][j][nr] = vl;
                        parj[i][j][nr] = pj;
                        parr[i][j][nr] = rp;
                        mv[i][j][nr] = 'R';
                    }
                }
            }
            if (j + 1 <= m) {
                int pj = j + 1;
                for (int rp = 0; rp < k + 1; rp++) if (dp[i + 1][pj][rp] > -inf) {
                    int nr = (rp + v) % (k + 1);
                    int vl = dp[i + 1][pj][rp] + v;
                    if (vl > dp[i][j][nr]) {
                        dp[i][j][nr] = vl;
                        parj[i][j][nr] = pj;
                        parr[i][j][nr] = rp;
                        mv[i][j][nr] = 'L';
                    }
                }
            }
        }
    }
    int bt = -inf, topc = -1;
    for (int j = 1; j <= m; j++) {
        if (dp[1][j][0] > bt) {
            bt = dp[1][j][0];
            topc = j;
        }
    }
    if (bt == -inf) {
        cout << -1 << "\n";
        return;
    }
    // 路径还原
    string path;
    int i = 1, j = topc, r = 0;
    while (i != n) {
        char c = mv[i][j][r];
        int pj = parj[i][j][r];
        int pr = parr[i][j][r];
        path.push_back(c);
        i = i + 1;
        j = pj;
        r = pr;
    }
    int col = j;
    reverse(path.begin(), path.end());
    cout << bt << "\n";
    cout << col << "\n";
    cout << path << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

这里也可以调整为 计数 ，对题目稍微修改一下，并且去掉 路径还原 的部分，因为计数并不需要路径。

问题描述

给定一个 $n \times m$ 的数字网格（每格 $0 \sim 9$），以及整数 $k$ 。令 $K = k+1$ 。

可以从 最底行第 $n$ 行任意一列 出发，每一步只能走到上一行的斜对角：

• 上左：$(i,j)\to(i-1,j-1)$

• 上右：$(i,j)\to(i-1,j+1)$

一直走到第 $1$ 行（共走 $n-1$ 步），路径的 得分 为路径上数字之和。

请统计：得分 $\bmod K = 0$ 的路径条数。
由于答案很大，输出对 $10^9+7$ 取模的结果。

状态做一个修改即可：

$$dp_{i, j, r} = \text{到达格子 }(i,j)\text{ 且路径和 }\bmod K = r\text{ 的方案数} $$

初始化起点：$dp_{n,j,{a_{n, j} \bmod K}} = 1$ 。

转移（从下往上推）：

到达 $(i,j)$ 只能从 $(i+1, j-1)$ 或 $(i+1, j+1)$ 来：

令 $v=a_{i, j}$，则

$$dp_{i,j,{(r + v) \bmod K}} = (dp_{i + 1, j - 1, r} + dp_{i + 1, j + 1, r})(\bmod MOD) $$

答案为：

$$\text{ans}=\sum_{j=1}^{m} dp_{1, j, 0}(\bmod MOD) $$

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e2 + 10, inf = 1e9 + 10, mod = 1e9 + 7;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, k, dp[N][N][15], a[N][N];
inline void addmod(int &x, int y) {
    x += y;
    if (x >= mod) x -= mod;
}
inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c; cin >> c;
            a[i][j] = c - '0';
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) for (int r = 0; r < k + 1; r++) {
        dp[i][j][r] = 0;
    }
    for (int j = 1; j <= m; j++) {
        int r = a[n][j] % (k + 1);
        dp[n][j][r] = 1;
    }
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            int v = a[i][j];
            for (int rp = 0; rp < k + 1; rp++) {
                int nr = (rp + v) % (k + 1);
                if (j - 1 >= 1) addmod(dp[i][j][nr], dp[i + 1][j - 1][rp]);
                if (j + 1 <= m) addmod(dp[i][j][nr], dp[i + 1][j + 1][rp]);
            }
        }
    }
    int Ans = 0;
    for (int j = 1; j <= m; j++) addmod(Ans, dp[1][j][0]);
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

3、四方向网格最值（可上 / 下 / 左 / 右，但步数有限）

题目描述

你正在 2050 会议的探索者空间中漫步。

探索者空间可以看作一个大小为 $n\times m$ 的无向带权网格图。顶点集合为 $\{(i, j)\mid 1\le i\le n, 1\le j\le m\}$。当且仅当 $|i_1-i_2|+|j_1-j_2|=1$ 时，顶点 $(i_1,j_1)$ 和 $(i_2, j_2)$ 之间有一条边相连。

每一步，你可以从当前位置走到与之相连的任意一个顶点。每条边上都有若干展品。由于你已经了解了所有展品，每当你经过一条包含 $x$ 个展品的边时，你的 无聊度 会增加 $x$。

对于每一个起点 $(i, j)$，请回答如下问题：如果你从 $(i, j)$ 出发，恰好走 $k$ 步后回到 $(i, j)$，最小可能的无聊度是多少？

你可以多次经过同一条边，但每次经过时该边上的无聊度都会被计入多次。每一步你都不能停留在当前位置，也不能在经过一条边时中途改变方向。在回到起点 $(i, j)$ 之前，你可以自由地访问 $(i, j)$（也可以不访问）。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$（$2\leq n, m\leq 500, 1\leq k\leq 20$）。

接下来的 $n$ 行中，第 $i$ 行的第 $j$ 个数（$1\le j \le m-1$）表示顶点 $(i, j)$ 和顶点 $(i, j+1)$ 之间的边上有多少展品。

接下来的 $n-1$ 行中，第 $i$ 行的第 $j$ 个数（$1\le j\le m$）表示顶点 $(i, j)$ 和顶点 $(i+1, j)$ 之间的边上有多少展品。

每条边上的展品数是一个 $1$ 到 $10^6$ 之间的整数。

输出格式

输出 $n$ 行，每行 $m$ 个数。第 $i$ 行第 $j$ 个数 $answer_{ij}$ 表示从 $(i, j)$ 出发，恰好走 $k$ 步回到 $(i, j)$ 时最小可能的无聊度。

如果无法恰好走 $k$ 步回到 $(i, j)$，则 $answer_{ij}=-1$。

输入输出样例 #1

输入 #1

3 3 10
1 1
1 1
1 1
1 1 1
1 1 1

输出 #1

10 10 10
10 10 10
10 10 10

输入输出样例 #2

输入 #2

2 2 4
1
3
4 2

输出 #2

4 4
10 6

输入输出样例 #3

输入 #3

2 2 3
1
2
3 4

输出 #3

-1 -1
-1 -1

说明/提示

在第一个样例中，无论怎么走，答案始终为 $10$。

在第二个样例中，$answer_{21}=10$，路径为 $(2,1)\to(1,1)\to(1,2)\to(2,2)\to(2,1)$，无聊度为 $4+1+2+3=10$。

解题思路

首先 $k$ 为奇数必然无解，将网格按 $(i+j)$ 的奇偶染色，是一个二分图。每走一步都会从一种颜色跳到另一种颜色，所以走奇数步必然落在 另一种颜色 ，不可能回到原点（同色）。因此 $k$ 奇数时对所有格子都输出 $-1$ 。

根据上面的结论可以观察到从 $(i, j)$ 走到一定位置之后就必须折返回去，这样才能回到 $(i, j)$ 。所以说把问题拆解成两个部分： 总代价 = 前半段代价 + 后半段代价 。

关键转化：只算 $k/2$ 步，然后答案乘 $2$

设 $k=2t$（偶数）。

任意一条从起点 $s$ 出发、长度 $2t$ 回到 $s$ 的走法：

$$s=v_0\to v_1\to \cdots \to v_t = u \to \cdots \to v_{2t}=s $$

• 令 $C(s\to u, t)$ 为 从 $s$ 出发走 恰好 $t$ 步 到达 $u$ 的最小代价。

• 由于图是无向的，$C(u\to s, t)=C(s\to u, t)$ 。

那么任意闭合走法经过中点 $u$ 的总代价 $\ge C(s\to u,t)+C(u\to s,t)=2C(s\to u,t)\ge 2\min_u C(s\to u,t)$。

同时，可以取使 $\min_u C(s\to u,t)$ 达到最小的那个 $u$ ，走一条最优的 $t$ 步到 $u$ ，再沿同一条边序列原路返回 $t$ 步，得到一个 $2t$ 步闭合走法，总代价正好是 $2\min_u C(s\to u,t)$。

所以答案就是：

$$ans_s = 2 \cdot \min_{u} C(s\to u, t)$$

DP 定义与转移（这里只做 $t=k/2$ 步）

直接计算

$$dp_{step,i,j} = \min_{u} C\big((i,j)\to u,\ step\big) $$

也就是：从 $(i,j)$ 出发走恰好 step 步，走到任意点的最小代价 。

初始化：$dp_{0, i, j} = 0$（走 $0$ 步不花钱）

从 $(i,j)$ 走一步到邻居 $(x,y)$ ，再走剩下 $step-1$ 步：

$$dp_{step, i, j} = \min_{(x,y)\in N(i,j)} \Big( w((i,j),(x,y)) + dp_{step-1, x, y} \Big) $$

其中 $N(i,j)$ 是四邻格，边权由输入给出：水平边和竖直边。

最后输出答案：

• 若 $k$ 奇数：全 $-1$

• 否则：输出 $2\cdot dp[t][i][j]$

时间复杂度：$O(nm\cdot k)$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 5e2 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, k, rt[N][N], dn[N][N], dp[15][N][N];
int C(int step, int x, int y) {
    int Res = inf;
    // 上下左右
    if (x > 1) Res = min(Res, dn[x - 1][y] + dp[step - 1][x - 1][y]);
    if (x < n) Res = min(Res, dn[x][y] + dp[step - 1][x + 1][y]);
    if (y > 1) Res = min(Res, rt[x][y - 1] + dp[step - 1][x][y - 1]);
    if (y < m) Res = min(Res, rt[x][y] + dp[step - 1][x][y + 1]);
    return Res;
}
inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m - 1; j++) cin >> rt[i][j];
    for (int i = 1; i <= n - 1; i++) for (int j = 1; j <= m; j++) cin >> dn[i][j];
    if (k & 1) {
        for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cout << -1 << (j == m ? '\n' : ' ');
        return;
    }
    int t = k / 2;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dp[0][i][j] = 0;
    for (int step = 1; step <= t; step++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[step][i][j] = C(step, i, j);
            }
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cout << (2 * dp[t][i][j]) << (j == m ? '\n' : ' ');
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

滚动一下

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 5e2 + 10, inf = 1e9 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
int n, m, k, rt[N][N], dn[N][N], dp0[N][N], dp1[N][N];
int C(int x, int y) {
    int Res = inf;
    // 上下左右
    if (x > 1) Res = min(Res, dn[x - 1][y] + dp0[x - 1][y]);
    if (x < n) Res = min(Res, dn[x][y] + dp0[x + 1][y]);
    if (y > 1) Res = min(Res, rt[x][y - 1] + dp0[x][y - 1]);
    if (y < m) Res = min(Res, rt[x][y] + dp0[x][y + 1]);
    return Res;
}
inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m - 1; j++) cin >> rt[i][j];
    for (int i = 1; i <= n - 1; i++) for (int j = 1; j <= m; j++) cin >> dn[i][j];
    if (k & 1) {
        for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cout << -1 << (j == m ? '\n' : ' ');
        return;
    }
    int t = k / 2;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) dp0[i][j] = 0;
    for (int step = 1; step <= t; step++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp1[i][j] = inf;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp1[i][j] = C(i, j);
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp0[i][j] = dp1[i][j];
            }
        }
    }
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cout << (2 * dp0[i][j]) << (j == m ? '\n' : ' ');
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

4、带额外维度的路径 DP（余数 / 血量 / 次数 / 颜色）

上面的题目其实已经讲了类似的操作。
比如：
第一个类型中的其实就是维护一个 $2$ 和 $5$ 的情况，做两套 DP 即可，当然还有 $0$ 的特殊情况。
第二个类型中的其实就是维护一个余数 $r$ 的情况，非常标准的 额外维度的路径 DP 。

这里讲解一个 $\text{xor}$ 的问题。

题目描述

有一个大小为 $n \times m$ 的矩形网格。每个格子上写有一个数字；第 $(i, j)$ 个格子上的数字为 $a_{i, j}$。你的任务是计算从左上角格子 $(1, 1)$ 到右下角格子 $(n, m)$ 的路径数，要求满足以下约束：

• 你只能向右或向下移动。具体来说，从格子 $(i, j)$ 可以移动到 $(i, j + 1)$ 或 $(i + 1, j)$，目标格子不能超出网格范围。
• 从 $(1, 1)$ 到 $(n, m)$ 路径上所有数字的异或和必须等于 $k$（异或操作是按位异或，在 Java 或 C++ 中用 '^' 表示，在 Pascal 中用 "xor" 表示）。

请计算在给定网格中满足条件的路径数。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 20$，$0 \le k \le 10^{18}$）——网格的高度、宽度和目标异或值 $k$。

接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个元素为 $a_{i, j}$（$0 \le a_{i, j} \le 10^{18}$）。

输出格式

输出一个整数，表示从 $(1, 1)$ 到 $(n, m)$ 且异或和等于 $k$ 的路径数。

输入输出样例 #1

输入 #1

3 3 11
2 1 5
7 10 0
12 6 4

输出 #1

3

输入输出样例 #2

输入 #2

3 4 2
1 3 3 3
0 3 3 2
3 0 1 1

输出 #2

5

输入输出样例 #3

输入 #3

3 4 1000000000000000000
1 3 3 3
0 3 3 2
3 0 1 1

输出 #3

0

说明/提示

第一个样例的所有路径：

• $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$；
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$；
• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$。

第二个样例的所有路径：

• $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$；
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$；
• $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$；
• $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$；
• $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$。

解题思路

其实非常的直观，直接使用 $dp_{i, j, x}$ 记录即可

$$dp_{i, j, x} = \text{从起点 }(1,1)\text{ 走到格子 }(i,j)\text{ 的所有路径中，路径上格子值异或结果恰好等于 }x\text{ 的路径条数} $$

这里的 路径异或结果 一般约定为：

$$x = a_{1,1} \oplus a_{p_2} \oplus \cdots \oplus a_{i,j} $$

也就是 包含起点和终点格子值 的 $\text{xor}$ 。

初始化：$dp_{1, 1, {a_{1, 1}}} = 1,\quad 其它 x 为 0$ 。

转移（只能右 / 下）

到 $(i,j)$ 只能从 $(i-1,j)$ 或 $(i,j-1)$ 来。
如果到前驱的 $\text{xor}$ 是 $y$，走到 $(i,j)$ 后 $\text{xor}$ 变成 $y \oplus a_{i,j}$ 。

所以对每个 $y$ ：

$$dp_{i, j, {y\oplus a_{i,j}}} += dp_{i - 1, j, y}$$ $$dp_{i, j, {y\oplus a_{i,j}}} += dp_{i, j - 1, y}$$

最终答案为：$\text{ans} = dp_{n, m, k}$ 。

但是很明显 $0 \le k \le 10^{18}, 0 \le a_{i, j} \le 10^{18}$ ，那么 $x$ 的取值接近 $2^{20}$ ，数组直接 爆炸 。

但是可以观察到 $1 \le n, m \le 20$ ，数据量非常的小，另外根据移动的方法可以发现 到某个格子 $(i,j)$ 的路径条数 是：

$$\binom{i+j-2}{i-1}$$

所以 $(i,j)$ 处最多也只会出现这么多个 $\text{xor}$ 值（很多还会重复合并），直接对这部分的维度使用 $\text{map}$ 做 稀疏存储 即可。

对每个格子 ${i, j}$ 维护一张表：

$$mp[i][j] = { x \mapsto \text{到 }(i,j)\text{ 且 xor}=x\text{ 的路径数}} $$

转移时，把上、左两张表的每个 $\text{key}$（出现过的 $\text{xor}$）都 $(\oplus a_{i,j})$ 后加到当前表里。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 50 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
LL n, m, k, a[N][N];
map<LL, LL> mp[N][N];
inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    mp[1][1][a[1][1]] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;
            auto &cur = mp[i][j];
            if (i > 1) {
                for (auto &kv : mp[i - 1][j]) {
                    LL nx = kv.first ^ a[i][j];
                    cur[nx] += kv.second;
                }
            }
            if (j > 1) {
                for (auto &kv : mp[i][j - 1]) {
                    LL nx = kv.first ^ a[i][j];
                    cur[nx] += kv.second;
                }
            }
        }
    }
    cout << mp[n][m][k] << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

但是这个程序的时间复杂度是 $2^{n + m}$ 无法通过，对于这种类型的问题需要使用 折半 的方法。

观察到从 $(1, 1)$ 走到 $(n, m)$ 一共需要走 $T = (n - 1) + (m - 1) = n + m - 2 \le 38$ 。

折半：选一个中间步数 $d=\lfloor T/2\rfloor$ ，把路径拆成两段：

• 从起点走 $d$ 步 到某个 中间对角线 上的格子。
• 从终点反向走 $T-d$ 步 到同一个格子。

这样 两边 各自枚举规模约 $2^{19}$ ，完全可行。

折半怎么 拼 出 $\text{xor==k}$（最关键公式）

固定中间层（对角线）

从 $(1,1)$ 出发走了 $d$ 步后，一定满足：

$$i+j = 2+d$$

所以中间层就是这条对角线上的格子集合。

从 $(n,m)$ 反向走 $T-d$ 步后也会到达同一条对角线（因为 $n+m-(T-d)=d+2$）。

两段 $\text{xor}$ 的合并

设中间格子为 $v=(i,j)$ 。

• 前半段（起点 $\to v$）的 $\text{xor}$ 记为 $X_f$ ， 定义为包含 $v$ 的值。

• 后半段（终点 $\to v$ 反向走）$\text{xor}$ 记为 $X_b$ ，也 包含 $v$ 的值。

那么整条路径的 $\text{xor}$ 会把 $a_v$ 计算两次，需要再异或一次抵消：

$$X_f \oplus X_b \oplus a_v = k$$

所以：

$$X_f = k \oplus X_b \oplus a_v$$

做法就是：

• 先把所有 $(v, X_f)$ 的出现次数存起来。

• 再枚举后半段到达的 $(v, X_b)$ ，去查需要的 $X_f$ 数量并累加。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 50 + 10;
int read(){
    int x = 0,f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
LL n, m, k, a[N][N];
map<LL, LL> f[N][N], g[N][N];
inline void solve() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    int T = n + m - 2;
    int d = T / 2;
    int rd = T - d;
    f[1][1][a[1][1]] = 1;
    for (int s = 0; s < d; s++) {
        for (int i = 1; i <= n; i++) {
            int j = (s + 2) - i;
            if (j < 1 || j > m) continue;
            auto &mp = f[i][j];
            if (mp.empty()) continue;
            if (i + 1 <= n) {
                LL val = a[i + 1][j];
                auto &to = f[i + 1][j];
                for (auto &kv : mp) {
                    LL nx = kv.first ^ val;
                    to[nx] += kv.second;
                }
            }
            if (j + 1 <= m) {
                LL val = a[i][j + 1];
                auto &to = f[i][j + 1];
                for (auto &kv : mp) {
                    LL nx = kv.first ^ val;
                    to[nx] += kv.second;
                }
            }
        }
    }
    g[n][m][a[n][m]] = 1;
    for (int t = 0; t < rd; t++) {
        for (int i = 1; i <= n; i++) {
            int j = (n + m) - t - i;
            if (j < 1 || j > m) continue;
            auto &mp = g[i][j];
            if (mp.empty()) continue;
            if (i - 1 >= 1) {
                LL val = a[i - 1][j];
                auto &to = g[i - 1][j];
                for (auto &kv : mp) {
                    LL nx = kv.first ^ val;
                    to[nx] += kv.second;
                }
            }
            if (j - 1 >= 1) {
                LL val = a[i][j - 1];
                auto &to = g[i][j - 1];
                for (auto &kv : mp) {
                    LL nx = kv.first ^ val;
                    to[nx] += kv.second;
                }
            }
        }
    }
    LL Ans = 0;
    for (int i = 1; i <= n; i++) {
        int j = (d + 2) - i;
        if (j < 1 || j > m) continue;
        auto &mf = f[i][j];
        auto &mg = g[i][j];
        if (mf.empty() || mg.empty()) continue;
        LL mid = a[i][j];
        for (auto &kv : mg) {
            LL xb = kv.first;
            LL cntb = kv.second;
            LL need = k ^ xb ^ mid;
            auto it = mf.find(need);
            if (it != mf.end()) Ans += cntb * it->second;
        }
    }
    cout << Ans << "\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}