Oiclass P1240 题解

这道题是真的难啊

这道题目中 \(\Huge 相邻\) 这个该 * 的词很容易 让人误以为这道题有后效性，当时我们全班都认为这道题有后效性，然而我们美丽的又和蔼的 Lily 却和我们说没有。仔细分析后发现，直接观察确实这道题目有后效性，但是如果深入分析，就会发现，只有前面的一项会影响它本身，在计算后一项的时候，对他本身并不会产生影响，他始终是最优解，行，确定能用 DP 了，开工！！！！

1. 划分阶段

划分阶段还算简单，一共有 \(n \times m\) 个阶段，也就是说每个房间一个。

2. 确定状态和状态变量

状态全部存储在二维数组 \(f\) 里面，\(f_{i,\ j}\) 就表示在第 \(i\) 层第 \(j\) 间房的最优解，即盖章的最小费用

3. 写状态转移方程

对于一个状态 \(f_{i,\ j}\) 他可以继承自他的 下、 左 、右 三个方向，为什么不能从上面？——你去问小胖啊，反正就是不行（doge）。

针对这三种方式，我们有以下的方程： \[ \left\{ \begin{array}{lr} f_{i,\ j} = f_{i-1,\ j} + a_{i,\ j}\ \ (上)\\ f_{i,\ j} = f_{i,\ j - 1} + a_{i,\ j}\ \ (左)\\ f_{i,\ j} = f_{i,\ j + 1} + a_{i,\ j}\ \ (右) \end{array} \right. \]

那么我们只需要取这几种之中的最小值就可以了。所以我们可以用 \(\min\) 函数吗？——不行，我们还要输出路径啊啊啊啊啊啊啊，我真的会谢。输出路径的话我们就还需要一个数组 \(pre\) 用来存储路径，正常我们在存储的时候都是存储上一项的下标，但是我们在这里没有办法存下标，所以我们有一种很巧妙的方法，刚刚我们不是有方向吗？那么我们直接把方向存进去，输出的时候根据方向算方位就行了，我真是个大聪明。那么就可以愉快的进入下一步了

4. 初始状态

初始状态很简单，因为走到一楼的任何一个房间都不需要路过任何一个房间，所以初始状态就是这样的的： \[ f_{1,\ j} = a_{1,\ j} \]

然后你可别忘记我们还有一个叫做 \(pre\) 的默默无闻的（垃圾） 数组，他也是要初始值的啊。因为任何一个房间都有可能是最后一个房间，所以我们要把他们全部都标记成 \(-1\) 方便输出的时候判断是否到达最后一个房间

5. 实现

到了开心有愉快的实现环节咯！！！Nice！！

实现非常非常非常非常非常非常非常非常简单，按照分析模拟就可以了（就是有一点点长~~），如下：

#include <iostream>
#include <cstring>

using namespace std;

int n, m, p, minn = 2147483647, a[509][509], f[509][509], pre[509][509];

void print(int x, int y) {
    if (pre[x][y] == -1) {
        cout << y << endl;
        return;
    }
    if (pre[x][y] == 1) {
        print(x - 1, y);
    } else if (pre[x][y] == 2) {
        print(x, y - 1);
    } else if (pre[x][y] == 3) {
        print(x, y + 1);
    }
    cout << y << endl;
}

int main() {
    cin >> m >> n;
    memset(f, 127, sizeof f);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
            if (i == 1) {
                pre[1][j] = -1;
                f[1][j] = a[1][j];
            }
        }
    }
    for (int i = 2; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = f[i - 1][j] + a[i][j];
            pre[i][j] = 1;
        }
        for (int j = 2; j <= n; j++) {
            if (f[i][j - 1] + a[i][j] < f[i][j]) {
                f[i][j] = f[i][j - 1] + a[i][j];
                pre[i][j] = 2;
            }
        }
        for (int j = n - 1; j >= 1; j--) {
            if (f[i][j + 1] + a[i][j] < f[i][j]) {
                f[i][j] = f[i][j + 1] + a[i][j];
                pre[i][j] = 3;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (minn > f[m][i]) {
            minn = f[m][i];
            p = i;
        }
    }
    print(m, p);
}