学术
浅谈棋盘类DP（五）
_Separation WA的一声就哭了 SU @ 2026-1-18 11:40:20

棋盘类 DP （两个人同步走 / 两条路径并行类型）

经典「两人同步走」网格 DP

首先补一下上一章的问题，每一个格子算一次的情况。

题目大意

在 $n\times n$ 网格上，Furik 从 $(1,1)\to(n,n)$ （只能下 / 右），Rubik 从 $(n,n)\to(1,1)$ （只能上 / 左）。最终得分是 两人走过的格子权值之和（每个格子只计一次） 。

解题思路

首先把 Rubik 的路反向：

Rubik 的路径从 $(n,n)$ 到 $(1,1)$ （上 / 左），反过来看就是一条从 $(1,1)$ 到 $(n,n)$ （下 / 右）的路径。

从 $(1,1)$ 走到任意格子 $(i,j)$ 的步数固定为

t=(i-1)+(j-1)

因此如果两条单调路径都经过同一个格子 $(i,j)$ ，它们一定发生在 同一个步数 $t$ （同一层对角线）。

所以 重复计数 只会发生在 同一步同格 ，用当步去重就够了。

剩下的就是和上一章节所讲的模型相同，只需要调整一下每一个格子的贡献只计算一次即可。

令

s = x+y \quad (\text{对角线层号})

起点 $(1,1)\Rightarrow s=2$ ，终点 $(n,n)\Rightarrow s=2n$ 。

定义：

$$dp[s][x_1][x_2] = \text{走到第 }s\text{ 层时，两人分别在 }(x_1,y_1),(x_2,y_2)\text{ 的最大得分} $$

其中

y_1=s-x_1,\quad y_2=s-x_2

并要求 $1\le y_1,y_2\le n$ 。

转移（ $4$ 种前驱）

从第 $s-1$ 层到第 $s$ 层，每个人要么向下（ $x$ 增 $1$ ），要么向右（ $y$ 增 $1$ ）。

在 $x$ 维度里等价为：

本层的 $x$ 若来自 上方格子 ，前一层是 $x-1$
本层的 $x$ 若来自 左方格子 ，前一层还是 $x$

所以前驱组合一共 $4$ 种：

$$(x_1,x_2)\leftarrow (x_1,x_2),\ (x_1-1,x_2),\ (x_1,x_2-1),\ (x_1-1,x_2-1) $$

本层加分（同格只加一次）：

$$gain = a_{x_1,y_1} + a_{x_2,y_2} - \mathbf{1}_{(x_1,y_1)=(x_2,y_2)}\cdot a_{x_1,y_1} $$

因此转移为：

dp[s][x_1][x_2] = \max(\text{四个前驱}) + gain

初始化：

dp[2][1][1]=a_{1,1}

答案：

dp[2n][n][n]

这里为了节省空间，直接用滚动数组降低到 $O(n^2)$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 3e2 + 10;
const LL inf = (1LL << 60);
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;
LL a[N][N];
LL pre[N][N], cur[N][N];
inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) pre[i][j] = -inf;
    pre[1][1] = a[1][1]; // s = 2
    for (int s = 3; s <= 2 * n; s++) {
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cur[i][j] = -inf;
        int xl = max(1, s - n);
        int xr = min(n, s - 1);
        for (int x1 = xl; x1 <= xr; x1++) {
            int y1 = s - x1;
            for (int x2 = xl; x2 <= xr; x2++) {
                int y2 = s - x2;
                LL best = pre[x1][x2];
                if (x1 > 1) best = max(best, pre[x1 - 1][x2]);
                if (x2 > 1) best = max(best, pre[x1][x2 - 1]);
                if (x1 > 1 && x2 > 1) best = max(best, pre[x1 - 1][x2 - 1]);
                if (best == -inf) continue;
                LL gain = a[x1][y1];
                if (!(x1 == x2 && y1 == y2)) gain += a[x2][y2];
                cur[x1][x2] = best + gain;
            }
        }
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) pre[i][j] = cur[i][j];
    }
    printf("%lld\n", pre[n][n]);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

那么接下来讲解一下 变形问题 ，比如：

起点不同，终点不同两人走。
图上两人走。
多人走。

起点不同，终点不同两人走

问题概述

给一个 $n\times m$ 的权值网格 $a_{i,j}$ 。有两个人：

Iahub：从 $(1,1)$ 出发走到 $(n,m)$ ，每步只能向下或向右；
Iahubina：从 $(n,1)$ 出发走到 $(1,m)$ ，每步只能向上或向右。

要求他们的两条路径 恰好有且只有一个公共格子 ，并且这个公共格子是 会面点 ：两人在该格子 不获得 该格子的权值（不锻炼，只聊天），然后继续走。目标是让两人获得的权值总和最大。

暴力美学

直接枚举所有路径，时间复杂度 $O(\binom{n+m-2}{n-1})^2$ 。

这部分没有什么可以解释的，和 浅谈棋盘类DP（四） 里面的方法类似，具体看注释即可。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 20 + 10;
const LL inf = (1LL << 60);
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;
LL a[N][N];
bool inA[N * N];              // 标记 A 当前路径走过哪些格子
LL sumA_cur;                  // 当前 A 路径总和（包含相遇点的值，后面会扣掉）
LL Ans = -inf;
inline int id(int x, int y) { // 1 - index -> 0..n * m - 1
    return (x - 1) * m + (y - 1);
}
inline bool bad_meet(int x, int y) {
    // 相遇点不能是任何一个人的起点 / 终点（否则“相遇后继续走”不成立）
    if (x == 1 && y == 1) return true;      // Iahub 起点
    if (x == n && y == m) return true;      // Iahub 终点
    if (x == n && y == 1) return true;      // Iahubina 起点
    if (x == 1 && y == m) return true;      // Iahubina 终点
    return false;
}
// 枚举 B 的路径；同时统计与 A 的交集大小 overlap（剪枝：>1直接停）
void dfsB(int x, int y, LL sumB, int overlap, int mx, int my) {
    // 进入 (x, y) 时，看看是否与 A 相交
    if (inA[id(x, y)]) {
        overlap++;
        if (overlap > 1) return;     // 超过一个公共格子，直接剪枝
        mx = x; my = y;              // 记录相遇点
    }
    if (x == 1 && y == m) {
        if (overlap == 1 && !bad_meet(mx, my)) {
            // sumA_cur 和 sumB 都把相遇点 a[mx][my] 加进去了
            // 但相遇点两人都不 workout => 需要把它从总和里彻底去掉
            LL tot = sumA_cur + sumB - 2LL * a[mx][my];
            Ans = max(Ans, tot);
        }
        return;
    }
    // B：上 或 右
    if (x - 1 >= 1) dfsB(x - 1, y, sumB + a[x - 1][y], overlap, mx, my);
    if (y + 1 <= m) dfsB(x, y + 1, sumB + a[x][y + 1], overlap, mx, my);
}
// 枚举 A 的路径，并把它走过的格子打到 inA 里
void dfsA(int x, int y, LL sumA) {
    inA[id(x, y)] = true;
    if (x == n && y == m) {
        sumA_cur = sumA;
        // B 从 (n, 1) 出发
        dfsB(n, 1, a[n][1], 0, 0, 0);
        inA[id(x, y)] = false;
        return;
    }
    // A：下 或 右
    if (x + 1 <= n) dfsA(x + 1, y, sumA + a[x + 1][y]);
    if (y + 1 <= m) dfsA(x, y + 1, sumA + a[x][y + 1]);
    inA[id(x, y)] = false;
}
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    Ans = -inf;
    dfsA(1, 1, a[1][1]);
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

简单优化方案

从 相遇点 观察可以看出，对于 相遇点 $(i,j)$ 处两人都不停留 workout，而是 从某个方向进来、从某个方向出去 。

这样子就可以将两条完整路径通过相遇点拆解成四条单人路径：

Iahub ： $(1,1)\to$ 相遇点附近、相遇点附近 $\to(n,m)$
Iahubina ： $(n,1)\to$ 相遇点附近、相遇点附近 $\to(1,m)$

正解

然后就可以看出，只需要针对 四个点往相遇点走 即可，其他代码就不写了，直接写正解。

使用四个 DP 表记录四种走法，然后枚举相遇点计算答案。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
const LL inf = (1LL << 60);
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;
LL a[N][N];
LL dp1[N][N], dp2[N][N], dp3[N][N], dp4[N][N];
inline void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> a[i][j];
    // d1: (1, 1) -> (i, j) (D / R)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp1[i][j] = a[i][j] + max(dp1[i - 1][j], dp1[i][j - 1]);
        }
    }
    // d2: (n, m) -> (i, j) (U / L)
    for (int i = n; i >= 1; i--) {
        for (int j = m; j >= 1; j--) {
            dp2[i][j] = a[i][j] + max(dp2[i + 1][j], dp2[i][j + 1]);
        }
    }
    // d3: (n, 1) -> (i, j) (U / R)
    for (int i = n; i >= 1; i--) {
        for (int j = 1; j <= m; j++) {
            dp3[i][j] = a[i][j] + max(dp3[i + 1][j], dp3[i][j - 1]);
        }
    }
    // d4: (1, m) -> (i, j) (D / L)
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            dp4[i][j] = a[i][j] + max(dp4[i - 1][j], dp4[i][j + 1]);
        }
    }
    LL Ans = 0;
    // 枚举相遇点 (i, j)，必须是内部点
    for (int i = 2; i <= n - 1; i++) {
        for (int j = 2; j <= m - 1; j++) {
            // 拼法 A（一个左右穿过，一个上下穿过）
            LL v1 = dp1[i][j - 1] + dp2[i][j + 1] + dp3[i + 1][j] + dp4[i - 1][j];
            // 拼法 B（交换上下 / 左右）
            LL v2 = dp1[i - 1][j] + dp2[i + 1][j] + dp3[i][j - 1] + dp4[i][j + 1];
            Ans = max(Ans, max(v1, v2));
        }
    }
    printf("%lld\n", Ans);
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

图上两人走（可调边权）

题目概述

给定一个有向图，有 $n$ 个点、 $m+k$ 条有向边（允许重边和自环）。有两名玩家：

Levko 起点在 $s_1$
Zenyk 起点在 $s_2$
目标都是到达终点 $f$

两人 同时出发、速度相同 ，并且都 最优地选择路线 （等价于在当前边权下走最短路）。谁先到 $f$ 谁赢；同时到则平局。保证从 $s_1,s_2$ 都能到达 $f$ 。

其中：

有 $m$ 条边边权固定；
有 $k$ 条边的边权 Levko 可以在比赛前重建设置为任意整数 $w_i\in[l_i,r_i]$ 。

任务：判断 Levko 是否能通过选择这 $k$ 条可变边的边权，使得比赛结果为：

"WIN"：Levko 必胜（到达时间严格小于 Zenyk）
"DRAW"：无法必胜但能保证平局
"LOSE"：无论怎么设置都会输

若答案为 "WIN" 或 "DRAW"，还要输出你为这 $k$ 条可变边选择的具体边权（按输入顺序）。

依旧暴力美学

把所有可变边的长度都枚举出来，每种赋值下跑一次最短路，比较两个人到 $f$ 的最短距离决定输赢。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 50 + 10;
const LL inf = (1LL << 60);
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;
}
struct Ed {
    int u, v;
    LL w, l, r;
    int var; // 0 fixed, 1 variable
};
int n, m, k;
int s1, s2, fz;
vector<Ed> e;
vector<vector<int>> revg;   // revg[v] 存所有 (u->v) 边的 idx
vector<int> vidx;           // 可变边下标
vector<LL> distv;           // dist to f (在反图从 f 跑)
vector<LL> best;
bool win = false, draw = false;
inline void dij() {
    distv.assign(n + 1, inf);
    priority_queue<pair<LL,int>, vector<pair<LL,int>>, greater<pair<LL,int>>> pq;
    distv[fz] = 0;
    pq.push({0, fz});
    while (!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        if (d != distv[x]) continue;
        for (int id : revg[x]) {
            int to = e[id].u;     // 反图：x(=v) -> u
            LL w = e[id].w;
            if (distv[to] > d + w) {
                distv[to] = d + w;
                pq.push({distv[to], to});
            }
        }
    }
}
inline void save_now() {
    best.clear();
    for (int id : vidx) best.push_back(e[id].w);
}
void dfs(int p) {
    if (win) return; // 已经找到 WIN，直接剪枝
    if (p == (int)vidx.size()) {
        dij();
        LL d1 = distv[s1], d2 = distv[s2];
        if (d1 < d2) {
            win = true;
            save_now();
        } else if (d1 == d2) {
            if (!draw) { // 只保存第一次 DRAW（且前面没有 WIN）
                draw = true;
                save_now();
            }
        }
        return;
    }
    int id = vidx[p];
    for (LL w = e[id].l; w <= e[id].r; w++) {
        e[id].w = w;
        dfs(p + 1);
        if (win) return;
    }
}
inline void solve() {
    cin >> n >> m >> k;
    cin >> s1 >> s2 >> fz;
    e.clear();
    vidx.clear();
    best.clear();
    win = draw = false;
    revg.assign(n + 1, vector<int>());
    for (int i = 1; i <= m; i++) {
        int a, b; LL c;
        cin >> a >> b >> c;
        int idx = (int)e.size();
        e.push_back({a, b, c, 0, 0, 0});
        revg[b].push_back(idx);
    }
    for (int i = 1; i <= k; i++) {
        int a, b; LL l, r;
        cin >> a >> b >> l >> r;
        int idx = (int)e.size();
        e.push_back({a, b, l, l, r, 1}); // 初始取 l
        revg[b].push_back(idx);
        vidx.push_back(idx);
    }
    dfs(0);
    if (win) {
        cout << "WIN\n";
        for (int i = 0; i < (int)best.size(); i++) {
            if (i) cout << ' ';
            cout << best[i];
        }
        cout << "\n";
    } else if (draw) {
        cout << "DRAW\n";
        for (int i = 0; i < (int)best.size(); i++) {
            if (i) cout << ' ';
            cout << best[i];
        }
        cout << "\n";
    } else {
        cout << "LOSE\n";
    }
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

解题思路

暴力必然超时，而且爆炸，那么该如何思考呢？

脑袋宕机！！！

直接把题目改了看看 ：

给定一个有向图，有 $n$ 个点、 $m$ 条有向边（允许重边和自环）。有两名玩家：

Levko 起点在 $s_1$
Zenyk 起点在 $s_2$
目标都是到达终点 $f$

任务：判断比赛结果为：

"WIN"：Levko 必胜（到达时间严格小于 Zenyk）
"DRAW"：无法必胜但能保证平局
"LOSE"：无论怎么设置都会输

那就相当于在固定有向带权图上，比较两个人到终点 $f$ 的最短路长度：

若 $dist(s_1,f) < dist(s_2,f)$ 输出 WIN
若 $dist(s_1,f) = dist(s_2,f)$ 输出 DRAW
否则输出 LOSE

wo直接 在反图从 $f$ 跑一次 Dijkstra ，得到所有点到 $f$ 的最短路，然后直接比较 $dist_{s_1}$ 和 $dist_{s_2}$ 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = (1LL << 60);
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;
}
struct Ed {
    int u, v;
    LL w;
};
int n, m;
int s1, s2, fz;
vector<Ed> e;
vector<vector<int>> revg;
vector<LL> distv;
inline void dij() {
    distv.assign(n + 1, inf);
    priority_queue<pair<LL,int>, vector<pair<LL,int>>, greater<pair<LL,int>>> pq;
    distv[fz] = 0;
    pq.push({0, fz});
    while (!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        if (d != distv[x]) continue;
        for (int id : revg[x]) {
            int to = e[id].u;
            LL w = e[id].w;
            if (distv[to] > d + w) {
                distv[to] = d + w;
                pq.push({distv[to], to});
            }
        }
    }
}
inline void solve() {
    cin >> n >> m;
    cin >> s1 >> s2 >> fz;
    e.clear();
    revg.assign(n + 1, {});
    for (int i = 1; i <= m; i++) {
        int a, b; LL c;
        cin >> a >> b >> c;
        int idx = (int)e.size();
        e.push_back({a, b, c});
        revg[b].push_back(idx);
    }
    dij();
    LL d1 = distv[s1], d2 = distv[s2];
    if (d1 < d2) cout << "WIN\n";
    else if (d1 == d2) cout << "DRAW\n";
    else cout << "LOSE\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

那么加入 $k$ 条可变边后：你是在 选边权，让比较结果变好 。

现在每条可变边 $i$ 的权值是能选的参数：

w_i\in[l_i,r_i]

Levko 要在开跑前把所有 $w_i$ 选好，然后两个人仍然各自走最短路。
所以本质是一个 离散优化问题 ：

$$\text{选择 }(w_1,\dots,w_k)\ \text{使得 }\mathrm{dist}(s_1,f)<\mathrm{dist}(s_2,f)\ (\text{或 }\le) $$

关键要找结构：怎么选才肯定不吃亏 。

这里涉及到贪心的策略：

如果你在某个点 $a$ 已经比对方先到（领先了 $\Delta>0$ ），那么从 $a$ 开始哪怕你把后面的路修得更快，对方要想利用这条 更快的路 ，也必须 先追到 $a$ ；但他到 $a$ 本来就晚，所以 不可能因为这条边变短就反超你 。

证明：

设在当前边权下：

$$D_1[a]=\text{Levko 从 }s_1\text{ 到 }a\text{ 的最短时间} $$$$D_2[a]=\text{Zenyk 从 }s_2\text{ 到 }a\text{ 的最短时间} $$

你在点 $a$ 已经领先 就是：

D_1[a] < D_2[a]

领先量 $\Delta = D_2[a]-D_1[a] > 0$ 。

这表示：不管对方怎么走，他最快也要到 $D_2[a]$ 才能到 $a$ ；而你最早 $D_1[a]$ 就到。

考虑一条可变边 $e: a\to b$ ，你把它的权值从 $r$ 降到 $l$ （变短了）。

对你（Levko）：

你能在 $D_1[a]$ 时刻到 $a$ ，走这条边后到 $b$ 的时间最多变成： $D_1[a] + l$ 变短当然只会让你更快 / 不变慢。

对对方（Zenyk）：

他要想利用这条变短的边，也得先到 $a$ 。但他最早到 $a$ 是 $D_2[a]$ 。
所以他使用这条边到 $b$ 的时间至少是：
$D_2[a] + l$

现在比较两人 通过这条边到 $b$ 的时间：

D_1[a] + l \quad \text{vs}\quad D_2[a] + l

因为 $D_1[a] < D_2[a]$ ，两边同时加同一个 $l$ 后仍然严格小：

D_1[a] + l < D_2[a] + l

结论： 即使对方也走这条变短的边，他通过这条边到达后继点仍然比你晚，领先不会被抹平，更不可能反超。

如果对方 不经过 $a$ ，靠别的路到终点更快，这也不会因为你 把从 $a$ 出发的边变短 而变得更糟：

你改变的是 从 $a$ 出发 的某些边；
这类改变只会影响那些路径中 包含 (a) 的最短路；
如果对方的最短路根本不经过 $a$ ，他不会获得任何收益；
如果经过 $a$ ，那他到 $a$ 还是晚于你，收益也只会 同步加速 ，无法翻盘。

所以安全的意思是： 这一步调整不会让你的赢面变差，只可能变好或不变。

领先发生在进入某个点之前的路段。
把领先点之后的路修得更快，相当于把你和对方在同一个起点 $a$ 后面一起加速；但对方没法绕过先到 $a$ 这个门槛。

总结

综上所述可以把一些边从 $r\to l$ 会改变最短路，从而让更多点满足 领先 / 不落后 ，所以要重复：

先把所有可变边设成 $r_i$ ；
跑 Dijkstra 得到 $d_1[\cdot], d_2[\cdot]$ ；
对满足条件的可变边（看它的出点 $a$ ）把 $w_i$ 从 $r_i$ 改 $l_i$ ；
重复 $2 \sim 3$ 直到本轮没有任何边再改变（稳定）。

每条可变边最多改一次，所以最多循环 $k+1$ 轮。

最终：

用 **严格版 $<$ ** 迭代稳定后，若
$d_1[f] < d_2[f]$
输出 WIN 和当前所有可变边的权值。
否则用 **非严格版 $≤$ ** 再做一遍，若
$d_1[f] \le d_2[f]$
输出 DRAW 和权值。
两者都不行输出 LOSE。

时间复杂度

每轮两次 Dijkstra，最多 $k+1$ 轮：

O\big(k\cdot (m+k)\log n\big)

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
const LL inf = (1LL << 60);
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;
}
struct Ed {
    int u, v;
    LL w, l, r;
    int var;
};
int n, m, k;
int s1, s2, fz;
vector<Ed> e;
vector<vector<int>> g;
vector<int> vid;
inline vector<LL> dij(int src) {
    vector<LL> dis(n + 1, inf);
    priority_queue<pair<LL,int>, vector<pair<LL,int>>, greater<pair<LL,int>>> pq;
    dis[src] = 0;
    pq.push({0, src});
    while (!pq.empty()) {
        auto [d, x] = pq.top(); pq.pop();
        if (d != dis[x]) continue;
        for (int id : g[x]) {
            int to = e[id].v;
            LL w = e[id].w;
            if (dis[to] > d + w) {
                dis[to] = d + w;
                pq.push({dis[to], to});
            }
        }
    }
    return dis;
}
inline bool process(int strict, vector<LL> &ans) {
    for (int id : vid) e[id].w = e[id].r;
    while (1) {
        vector<LL> d1 = dij(s1);
        vector<LL> d2 = dij(s2);
        bool ch = false;
        for (int id : vid) {
            if (e[id].w == e[id].l) continue;
            int a = e[id].u;
            if ((strict && d1[a] < d2[a]) || (!strict && d1[a] <= d2[a])) {
                e[id].w = e[id].l;
                ch = true;
            }
        }
        if (!ch) {
            bool ok = strict ? (d1[fz] < d2[fz]) : (d1[fz] <= d2[fz]);
            if (!ok) return false;
            ans.clear();
            for (int id : vid) ans.push_back(e[id].w);
            return true;
        }
    }
}
inline void solve() {
    cin >> n >> m >> k;
    cin >> s1 >> s2 >> fz;
    e.clear();
    g.assign(n + 1, {});
    vid.clear();
    vid.reserve(k);
    for (int i = 1; i <= m; i++) {
        int a, b; LL c;
        cin >> a >> b >> c;
        int idx = (int)e.size();
        e.push_back({a, b, c, 0, 0, 0});
        g[a].push_back(idx);
    }
    for (int i = 1; i <= k; i++) {
        int a, b; LL l, r;
        cin >> a >> b >> l >> r;
        int idx = (int)e.size();
        e.push_back({a, b, r, l, r, 1});
        g[a].push_back(idx);
        vid.push_back(idx);
    }
    vector<LL> Ans;
    // WIN
    if (process(1, Ans)) {
        cout << "WIN\n";
        for (int i = 0; i < (int)Ans.size(); i++) {
            if (i) cout << ' ';
            cout << Ans[i];
        }
        cout << "\n";
        return;
    }
    // DRAW
    if (process(0, Ans)) {
        cout << "DRAW\n";
        for (int i = 0; i < (int)Ans.size(); i++) {
            if (i) cout << ' ';
            cout << Ans[i];
        }
        cout << "\n";
        return;
    }
    cout << "LOSE\n";
}
int main() {
    int _ = 1;
    while (_--) solve();
    return 0;
}

多人走

题目概述

给你一个 $n \times m$ 的网格：

每个格子有颜色 $c_{i,j}\in{0,1}$ ：0 表示黑格，1 表示白格；
每个格子还有一个方向 $s_{i,j}\in{\text{U,R,D,L}}$ ，表示从该格子会指向相邻的一个格子（相当于每个点出度为 $1$ 的有向图）。并保证边界不会指到网格外。

你要在一些格子里放机器人（每格最多 $1$ 个），然后机器人会 同步无限次移动 ：每一秒每个机器人必须沿着所在格子的方向走到相邻格。

要求：

在任何时刻（更严格说：在每次移动之前），不能出现两个机器人在同一个格子里（包括初始时刻也不行）。
机器人会一直走（无限步）。

目标是两级优化：

第一目标：放下的机器人数量尽可能多；
第二目标：在机器人数量已经最大化的前提下，让 初始时刻站在黑格（0）上的机器人数量 尽可能多。

解题思路

如果只看 第一目标：最多能放多少机器人 ，答案其实就是 网格函数图（内向基环树）里所有环上的点的数量（出度恒为 $1$ ，把所有入度为 $0$ 的点不断剥掉，剩下的全是环点）。

这种玩意（内向基环树）有两个常用的结论：

结论 A：怎么找环？

用 拓扑剥叶 （Kahn）：

统计入度
把入度为 0 的点不断删掉
剩下的点全在环上

这也是本题第一目标的做法。

结论 B：怎么处理非环部分？

把边反向，从环点做 BFS / DFS，就能遍历 挂在环上的树 ，做树 DP、统计深度、计数方案等。

这个结构具体长什么样子可以百度搜一下，就很容易理解为什么有这两个结论了。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e3 + 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, toV[N], indeg[N], q[N];
char c[N][N], s[N][N];
inline int id(int x, int y) {return (x - 1) * m + y;}
inline void solve() {
    cin >> n >> m;
    int tot = n * m;
    for (int i = 1; i <= n; i++) scanf("%s", c[i] + 1);
    for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);
    for (int i = 1; i <= tot; i++) indeg[i] = 0;
    // 建出边 + 入度
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int u = id(i, j);
            char d = s[i][j];
            int v = u;
            if (d == 'U') v = id(i - 1, j);
            else if (d == 'D') v = id(i + 1, j);
            else if (d == 'L') v = id(i, j - 1);
            else if (d == 'R') v = id(i, j + 1);
            toV[u] = v;
            indeg[v]++;
        }
    }
    // Kahn 剥叶：入度为 0 的点一定不在环上
    int hh = 0, tt = 0;
    for (int i = 1; i <= tot; i++) if (indeg[i] == 0) q[tt++] = i;
    int rem = 0;
    while (hh < tt) {
        int u = q[hh++];
        rem++;
        int v = toV[u];
        if (--indeg[v] == 0) q[tt++] = v;
    }
    int Ans = tot - rem; // 剩下全是环点 = 第一目标最大机器人数量
    printf("%d\n", Ans);
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

然后把网格看成 函数图（每点出度 $=1$ ）。对每个连通块（内向基环树）：

第一目标的最大机器人数量 $=$ 环长 $L$ （环上点数）。
为了让 $L$ 个机器人永远不撞车，本质是：它们进入环后的相位必须两两不同。

对块内任意点 $u$ ，定义：

$rt_u$ ： $u$ 最终进入的 环上的入口点 （第一次到达的环点）
$dist_u$ ： $u$ 到入口点的步数
$pos_x$ ：环上点 $x$ 在环中的编号 $0..L-1$

则这个点对应的“相位”：

key(u) \equiv pos(rt_u) - dist(u) \pmod L

性质：两机器人是否会在某时刻相撞 当且仅当 它们的 $key$ 相同（同一块内）。
因此在同一块里放满 $L$ 个机器人时，必须 每个余数 $0..L-1$ 各选一个起点 。

于是第二目标就变成：
对每个余数 $r$ ，只要存在一个黑点 $u$ 满足 $key(u)=r$ ，就能让该余数选黑点；否则只能选白点。
所以该块最多黑点数 = 有黑点覆盖的余数个数 。

#include <bits/stdc++.h>
#define LOG(FMT...) fprintf(stderr, FMT)
using namespace std;
typedef long long LL;
const int N = 1e6 + 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;
int toV[N], indeg[N];
int comp[N], rt[N], posi[N], dista[N];
char col[N];                 // '0'/'1'
int q[N];
vector<int> G[N];            // 反图：G[v] 存所有 u，使得 u->v
inline int id(int x, int y) { return (x - 1) * m + y; }
inline void solve() {
    cin >> n >> m;
    int tot = n * m;
    for (int i = 1; i <= tot; i++) {
        indeg[i] = 0;
        comp[i] = 0;
        G[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        for (int j = 1; j <= m; j++) {
            int u = id(i, j);
            col[u] = s[j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        for (int j = 1; j <= m; j++) {
            int u = id(i, j);
            char d = s[j - 1];
            int v = u;
            if (d == 'U') v = u - m;
            else if (d == 'D') v = u + m;
            else if (d == 'L') v = u - 1;
            else if (d == 'R') v = u + 1;
            toV[u] = v;
            indeg[v]++;
            G[v].push_back(u); // 反图：v <- u
        }
    }
    // 1) Kahn 剥叶：剩下 indeg>0 的点都在环上
    int hh = 0, tt = 0;
    for (int i = 1; i <= tot; i++) if (indeg[i] == 0) q[tt++] = i;
    while (hh < tt) {
        int u = q[hh++];
        int v = toV[u];
        if (--indeg[v] == 0) q[tt++] = v;
    }
    // 第一目标：总环点数
    int Ans1 = 0;
    for (int i = 1; i <= tot; i++) if (indeg[i] > 0) Ans1++;
    // 第二目标：每个环块统计“能用黑点覆盖的相位余数”个数
    int Ans2 = 0;
    for (int st = 1; st <= tot; st++) {
        if (indeg[st] == 0 || comp[st] != 0) continue; // 不是环点 or 已处理
        // 取出一个环（st 在环上）
        vector<int> cyc;
        int v = st;
        while (comp[v] == 0) {
            comp[v] = -1;            // 临时标记“在环上”
            cyc.push_back(v);
            v = toV[v];
        }
        int L = (int)cyc.size();
        // 环上编号 pos、rt、dist，并换成组件标记 = st
        for (int i = 0; i < L; i++) {
            int x = cyc[i];
            comp[x] = st;
            posi[x] = i;
            rt[x] = x;
            dista[x] = 0;
        }
        // seen[r]=1 表示余数 r 可以选到黑点作为该相位的代表
        vector<unsigned char> seen(L, 0);
        for (int i = 0; i < L; i++) {
            int x = cyc[i];
            if (col[x] == '0') seen[i] = 1; // key(x)=pos(x)
        }
        // BFS 反向扩展整棵入树
        hh = 0; tt = 0;
        for (int x : cyc) q[tt++] = x;
        while (hh < tt) {
            int x = q[hh++];
            for (int u : G[x]) {     // u -> x
                if (comp[u]) continue;
                comp[u] = st;
                rt[u] = rt[x];
                dista[u] = dista[x] + 1;
                int r = posi[rt[u]] - dista[u];
                r %= L; if (r < 0) r += L;
                if (col[u] == '0') seen[r] = 1;
                q[tt++] = u;
            }
        }
        // 该块最多黑点数 = seen 中 1 的个数
        for (int r = 0; r < L; r++) Ans2 += (seen[r] != 0);
    }
    cout << Ans1 << " " << Ans2 << "\n";
}
int main() {
    int _ = 1; cin >> _;
    while (_--) solve();
    return 0;
}

目前还没有评论...

浅谈棋盘类DP（五）

棋盘类 DP （两个人同步走 / 两条路径并行类型）

经典「两人同步走」网格 DP

题目大意

解题思路

定义：

转移（444 种前驱）

起点不同，终点不同两人走

问题概述

暴力美学

简单优化方案

正解

图上两人走（可调边权）

题目概述

依旧暴力美学

解题思路

证明：

对你（Levko）：

对对方（Zenyk）：

总结

最终：

时间复杂度

多人走

题目概述

解题思路

结论 A：怎么找环？

结论 B：怎么处理非环部分？

0 条评论

还没有账户？

登录

转移（ $4$ 种前驱）