P3133 [USACO16JAN]Radio Contact G 的题解

· · 题解

题目大意

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

思路

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

STEP1. 定义 dp 数组

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

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

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

STEP2. 设计状态转移

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

这题仍然不例外。

我们来 分情况讨论 (为了简便这里把 FJ 看成 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;
}