一篇题解

· · 题解

分析

看到这题，很容易想到 dp。

在不考虑牛每走三步便要吃一次草的情况下，对于每个点 (i,j)，可以由 (i-1,j),(i,j-1) 转移过来（由 (i+1,j),(i,j+1) 转移过来是没有意义的）。设 f_{i,j} 表示到达 (i,j) 所需的最短时间，则转移为 f_{i,j}=\min (f_{i-1,j},f_{i,j-1})+T。

接着考虑牛每走三步便要吃一次草的条件。

由于有步数限制，所以在 f 数组中增加一维，设 f_{i,j,k} 表示当前在 (i,j)，且走的步数对 3 取模的值为 k，所需的最短时间。

很显然的一个转移是由 (i,j) 走向相邻的点，且步数 k 加一。也即 f_{i,j,k} 可以转移到 f_{i-1,j,(k+1)\bmod 3},f_{i+1,j,(k+1)\bmod 3},f_{i,j-1,(k+1)\bmod 3},f_{i,j+1,(k+1)\bmod 3}（注意到此时相邻的四个点都应当被转移到，原因可从下文中理解）。

但是单纯的这样转移是错误的，因为这些步数对 3 取模的值是我们被动转移的。假设转移到终点 (n,n) 时，当前的步数刚好是 3 的步数，且在 (n,n) 吃草的时间相当长，还不如在其他地方多走几步，然后吃草再走到 (n,n)，那么此时的 dp 转移便是不完整的，错误的。

用上述反例思考另一个转移，我们可以用当前步数 k 转移到 k+1，那么是否可以转移到 k+2,k+3 呢？首先考虑 转移到 k+3，合理的策略是选择在其他位置来回走，消耗两步，再走到当前所需要转移的位置，此时需要分类讨论 k 对 3 取模的值，从而选出在吃草时所需花费的最短时间。以下伪代码以 (i,j) 转移到 (i+1,j) 为例：

int now = min(a[i - 1][j], a[i + 1][j]);
now = min(now, min(a[i][j + 1], a[i][j - 1]));
int tmp = 0;
if (k + 1 == 3)
    tmp = now;
else if (k + 2 == 3)
    tmp = a[i][j];
else if (k + 3 == 3)
    tmp = a[i + 1][j];
f[i + 1][j][k] = min(f[i + 1][j][k], f[i][j][k] + 3 * T + tmp);

在考虑是否可以转移到 k+2，由于从 (i,j) 走到需要转移的位置得花费一步，而剩下的一步是无法使用的，所以 k+2 无法转移到。且其他更多的情况可以由其他的 dp 状态转移到。

最后，考虑到这个转移是有后效性的，也就是说对于一个位置，在被之前的某个状态转移过来时，它对于其它的位置而言，此时可能是最优的。那么可以进行多次转移，对于最优秀的位置，它被“扩散”到、成为优秀的位置时，最多要进行 n 次整体转移；再由它向四周“扩散”最优情况时，最多要“扩散” n 次，所以整体转移是不超过 2n 次的。

当然，一个在考场上骗分的做法是直接转移 1000 次，很具有教育诱导意义。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[105][105];
int f[105][105][5];

signed main() {
    int n, T;
    cin >> n >> T;
    for (int i = 0; i <= 103; i++)
        for (int j = 0; j <= 103; j++)
            a[i][j] = f[i][j][0] = f[i][j][1] = f[i][j][2] = 100000000000000000;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    f[1][1][0] = 0;
    for (int ii = 1; ii <= 2 * n; ii++)
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 0; k < 3; k++) {
                    f[i + 1][j][(k + 1) % 3] = min(f[i + 1][j][(k + 1) % 3], f[i][j][k] + T + (k + 1 == 3) * a[i + 1][j]);
                    f[i][j + 1][(k + 1) % 3] = min(f[i][j + 1][(k + 1) % 3], f[i][j][k] + T + (k + 1 == 3) * a[i][j + 1]);
                    f[i - 1][j][(k + 1) % 3] = min(f[i - 1][j][(k + 1) % 3], f[i][j][k] + T + (k + 1 == 3) * a[i - 1][j]);
                    f[i][j - 1][(k + 1) % 3] = min(f[i][j - 1][(k + 1) % 3], f[i][j][k] + T + (k + 1 == 3) * a[i][j - 1]);
                    int now = min(a[i - 1][j], a[i + 1][j]);
                    now = min(now, min(a[i][j + 1], a[i][j - 1]));
                    int tmp = 0;
                    if (k + 1 == 3)
                        tmp = now;
                    else if (k + 2 == 3)
                        tmp = a[i][j];
                    else if (k + 3 == 3)
                        tmp = a[i + 1][j];
                    f[i + 1][j][k] = min(f[i + 1][j][k], f[i][j][k] + 3 * T + tmp);
                    tmp = 0;
                    if (k + 1 == 3)
                        tmp = now;
                    else if (k + 2 == 3)
                        tmp = a[i][j];
                    else if (k + 3 == 3)
                        tmp = a[i][j + 1];
                    f[i][j + 1][k] = min(f[i][j + 1][k], f[i][j][k] + 3 * T + tmp);
                    tmp = 0;
                    if (k + 1 == 3)
                        tmp = now;
                    else if (k + 2 == 3)
                        tmp = a[i][j];
                    else if (k + 3 == 3)
                        tmp = a[i][j - 1];
                    f[i][j - 1][k] = min(f[i][j - 1][k], f[i][j][k] + 3 * T + tmp);
                    tmp = 0;
                    if (k + 1 == 3)
                        tmp = now;
                    else if (k + 2 == 3)
                        tmp = a[i][j];
                    else if (k + 3 == 3)
                        tmp = a[i - 1][j];
                    f[i - 1][j][k] = min(f[i - 1][j][k], f[i][j][k] + 3 * T + tmp);
                }
            }
        }
    cout << min(f[n][n][0], min(f[n][n][1], f[n][n][2]));
}