专栏文章

P11952 行走 题解

ssunqihuan
P11952题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minir2vb
此快照首次捕获于
2025/12/02 03:05
3 个月前
此快照最后确认于
2025/12/02 03:05
3 个月前
查看原文
一道非常经典和锻炼人的 dp 题，建议一定好好做。
先理清题目：有一个网格，每条边都有一个边权，存储方式如下：
  • (x,y)(x,y) 到 (x,y+1)(x,y+1) 的边权存储在 ea(x,y)ea_{(x,y)} 里。
  • (x,y)(x,y) 到 (x+1,y)(x+1,y) 的边权存储在 eb(x,y)eb_{(x,y)} 里。
然后每次删去一条边，求最短路。
先放代码，思路最好结合来理解：
CPP
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
// 全局变量 seed 和 B
unsigned long long seed;
int B;

const long long N = 5005, inf = 1e16;

long long f[N][N], f2[N][N], ea[N][N], eb[N][N];

// xorshift64 算法，不能修改
unsigned long long xorshift64(){
    seed ^= seed << 13;
    seed ^= seed >> 7;
    seed ^= seed << 17;
    return seed;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	
    int n, q;
    cin >> n >> q;
	
    cin >> seed >> B;
	
    // 生成横向边权：遍历 i=1..n, j=1..n-1
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n-1; j++){
            xorshift64();
            ea[i][j] = seed & ((1ULL << B) - 1);
        }
    }
	
    // 生成纵向边权：遍历 i=1..n-1, j=1..n
    for (int i = 1; i <= n-1; i++){
        for (int j = 1; j <= n; j++){
            xorshift64();
            eb[i][j] = seed & ((1ULL << B) - 1);
        }
    }
    // 你可以从这里开始编写你的代码
    
    for (int i = 2; i <= n; i ++ ) f[1][i] = f[1][i - 1] + ea[1][i - 1];
    for (int i = 2; i <= n; i ++ ) f[i][1] = f[i - 1][1] + eb[i - 1][1];
    for (int i = n - 1; i >= 1; i -- ) f2[n][i] = f2[n][i + 1] + ea[n][i];
    for (int i = n - 1; i >= 1; i -- ) f2[i][n] = f2[i + 1][n] + eb[i][n];
    for (int i = 2; i <= n; i ++ )
    	for (int j = 2; j <= n; j ++ )
    		f[i][j] = min(f[i - 1][j] + eb[i - 1][j], f[i][j - 1] + ea[i][j - 1]);
    for (int i = n - 1; i >= 1; i -- )
    	for (int j = n - 1; j >= 1; j -- )
    		f2[i][j] = min(f2[i][j + 1] + ea[i][j], f2[i + 1][j] + eb[i][j]);
    for (int i = 0; i <= n + 1; i ++ )
    	for (int j = 0; j <= n + 1; j ++ )
    	{
    		if (i < 1 || j < 1 || i > n || j >= n) ea[i][j] = inf;
    		if (i < 1 || j < 1 || i >= n || j > n) eb[i][j] = inf;
		}    
    for (int j = 1; j <= n; j ++ )
    	for (int i = n; i >= 1; i -- )
    		ea[i][j] = min(ea[i + 1][j], f[i][j] + ea[i][j] + f2[i][j + 1]);
    for (int i = 1; i <= n; i ++ )
    	for (int j = n; j >= 1; j -- )
    		eb[i][j] = min(eb[i][j + 1], f[i][j] + eb[i][j] + f2[i + 1][j]);
    while (q -- )
    {
    	int x, y, xx, yy;
    	cin >> x >> y >> xx >> yy;
    	if (x == xx) cout << min(ea[x + 1][y], eb[x - 1][y + 1]) << "\n";
    	else cout << min(eb[x][y + 1], ea[x + 1][y - 1]) << "\n";
	}
    return 0;
}
如果没有删边的话，那这道题就是一道简单的动规题目，转移方程就是 fi,j=min⁡(fi−1,j+ebi−1,j,fi,j−1+eai,j−1)f_{i,j}=\min(f_{i-1,j}+eb_{i-1,j},f_{i,j-1}+ea_{i,j-1})
但是有删边。考虑到一定经过一条边 (x,y)(x2,y2)(x,y)(x_2,y_2) 的最小权值就是从起点到 (x,y)(x,y) 的最小权值加上边权加上从 (x2,y2)(x_2,y_2) 到终点的最小权值。所以想到要处理后缀，转移方程很相似。这样我们就写出了 ff 和 f2f_2 数组。
下一步就是在 eaea 和 ebeb 上做 dp，所以先把周围都清除成无穷大。（这里有一个坑点就是一开始 ea,ebea,eb 的大小只到 nn，如果再加一就会 RE，所以前面的定义要改）
这里的含义变了（重中之重！），设 ea/ebx,yea/eb_{x,y} 表示的意义为“跨越某条切口（横/纵）的最短绕行代价”，从直接穿过和向右/下绕行取最小值，所以转移方程显而易见。
接下来的难点是如何求答案。先看去掉 (x,y)(x,y+1)(x,y)(x,y+1) 的情况。
可以发现，想要绕过断掉的边，就只能在这两条边上不断向下/右绕，取最小值即可。
如果是断掉竖着的边那就整个反过来就行了，主要看代码。
感觉好像表达的并不是很通畅（？）如果有更多的意见和方法希望能在评论区留言，我也很希望能更深入理解这道题目。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...