自动搬运

查看原文

来自洛谷，原作者为

	卷王 可惜没如果.

搬运于2025-08-24 21:45:39，当前版本为作者最后更新于2023-03-21 20:28:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

点这里 感觉这题的题目描述得改改了。

思路

一遇到走路求最大值的问题我们首先会想到 dp。显然，这题不例外。让我们来探讨一下吧。

STEP1. 定义 dp 数组

我总结出橙黄的 dp 基本上都是问啥设啥。

这题也不例外。我们可以设 $dp_{i,j}$ 表示 FJ 走到路径的第 $i$ 个点，Bessie 走到路径的第 $j$ 个点时候最少消耗的能量。

好，就是这样。请读者们别急，让我们继续。

STEP2. 设计状态转移

橙黄题的状态转移基本上都是很基础、很简单的。

这题仍然不例外。

我们来 分情况讨论 (为了简便这里把 FJ 看成 F，把奶牛看成 B)：

• F走，B不走，即 $dp_{i - 1, j}$。
• F走，B走，即 $dp_{i - 1, j - 1}$。
• F不走，B走，即 $dp_{i, j - 1}$。
• F不走，B也不走，这种情况由于不走还不如走，所以去掉。

题目说要取最小的能量值，所以取 $\min$。

状态转移方程：$dp_{i, j} = \min(dp_{i - 1, j - 1}, dp_{i - 1, j}, dp_{i, j - 1}) + $ $\text{从 i 到 j 消耗的能量}$。

有人问，这个从 $i$ 到 $j$ 消耗的能量怎么求？别急，看下面 qwq。

我们开个结构体，设 $fx_i$ 表示 FJ 在他的路径上的第 $i$ 个步骤在 x 轴上的哪个位置，$fy_i$ 表示表示 FJ 在他的路径上的第 $i$ 个步骤在 y 轴上的哪个位置。$bx_i$ 与 $by_i$ 同理，只是把 FJ 换成 Bessie。在读入的时候根据字符依次判断即可。

有了这两个数组，那么就可以快速求出在某一时刻两人的距离，也就知道了从 $i$ 到 $j$ 消耗的能量。

解决，下一部分！

STEP3. 初始化

有人说，这个简单！不就是这个赋一下值，然后那个再改一下吗？

但是这个蒟蒻并不这么认为 qwq。

你如果想写好初始化，那么就必需深深地领会 dp 数组的意思和 dp 的本质，所以要扎实一点，现在没学好，后面就会很难理解了！

好，言归正传，我们讲题——

严格意义上，我们要先令 $dp[0][0] = 0$，但是由于 dp 数组本身就默认为 $0$，所以可以不写。

再回顾一下，我们的 $dp_{i,j}$ 表示 FJ 走到路径的第 $i$ 个点，Bessie 走到路径的第 $j$ 个点时候最少消耗的能量。

那么我们就必需初始 FJ 一直没动，或者 Bessie 一直没动消耗的能量。

怎么做？很简单，请自行思考。实在不行看代码吧。

AC CODE：

#include<bits/stdc++.h>
using namespace std;
int n, m;
int fx, fy, bx, by;
int dp[1007][1007];
//dp[i][j] 表示 FJ 走到路径的第 i 个点，Bessie 走到路径的第 j 个点时候最少消耗的能量 
struct node {
	int x, y;
}f[1007], b[1007]; //开两个数组记录路径 
inline int dis(int u, int v) { //计算两点需要消耗的能量 
	return pow(f[u].x - b[v].x, 2) + pow(f[u].y - b[v].y, 2);
}
int main() {
	cin >> n >> m >> fx >> fy >> bx >> by; //读入 
	f[0] = (node){fx, fy}; b[0] = (node){bx, by};
	for(int i = 1; i <= n; i++) { //FJ
		char c; cin >> c; //初始化，依次判断 
		if(c == 'N') f[i] = (node){f[i - 1].x, f[i - 1].y + 1}; //北，往右 
		if(c == 'E') f[i] = (node){f[i - 1].x + 1, f[i - 1].y}; //东，往下 
		if(c == 'S') f[i] = (node){f[i - 1].x, f[i - 1].y - 1}; //南，往左 
		if(c == 'W') f[i] = (node){f[i - 1].x - 1, f[i - 1].y}; //西，往上 
	}
	for(int i = 1; i <= m; i++) { //Bessie
		char c; cin >> c; //初始化，依次判断 
		if(c == 'N') b[i] = (node){b[i - 1].x, b[i - 1].y + 1}; //北，往右 
		if(c == 'E') b[i] = (node){b[i - 1].x + 1, b[i - 1].y}; //东，往下 
		if(c == 'S') b[i] = (node){b[i - 1].x, b[i - 1].y - 1}; //南，往左 
		if(c == 'W') b[i] = (node){b[i - 1].x - 1, b[i - 1].y}; //西，往上 
	}
	for(int i = 1; i <= n; i++) //dpの初始化 
		dp[i][0] = dp[i - 1][0] + dis(i, 0);
	for(int i = 1; i <= m; i++) //同理 
		dp[0][i] = dp[0][i - 1] + dis(0, i);
	for(int i = 1; i <= n; i++) //很简单的 dp 
		for(int j = 1; j <= m; j++)
			dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + dis(i, j);
	cout << dp[n][m];
	return 0;
}