[dp]危机合约-2018级算法C6-C题解

发表于 | 分类于 | 热度: 度

题目链接

本题中，每个格子的答案可以影响右上、右、右下 3 个格子的答案，显然可以推出状态转移方程为：
$$
dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i+1][j-1])
$$
推出状态转移方程后，本题还需要注意的细节有：

  1. dp 数组是一列一列地迭代出来的，所以循环时应该先循环列数再循环行数；
  2. 初始化时，需要注意应该同时初始化第 0 列为 INF，如果不初始化第 0 列为 INF，进行第一列的递推时应该只能考虑起点所影响到的 3 个格子；
  3. 不能走的点可以设置伤害为 INF，则必然不会计入答案中；
  4. 多个 INF 相加可能会溢出，注意考虑计算顺序；
  5. 本题的输入为字母数字混合式二维数组，注意到数字范围为 $0\sim 9$，这里可以使用 scanf("%1s", str); 的方式进行输入。这种输入方式为每次输入一个长度为 1 的字符串，而当输入字符串时会自动过滤空白字符，从而达到每次只输入一个非空白字符的目的。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

const int INF = 0x3f3f3f3f;
const int N = 100 + 5;
int dp[N][N], G[N][N];
char tmp[2];

int main() {
    int n, m;
    int h, a, b;
    scanf("%d%d%d%d%d", &n, &m, &h, &a, &b);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%1s", tmp);
            G[i][j] = (tmp[0] == '*' ? INF : tmp[0] - '0');
            dp[i][j] = INF;
        }
    for (int i = 1; i <= n; i++)
        dp[i][m + 1] = INF;

    int ans;
    for (int i = a - 1; i <= a + 1; i++)
        dp[i][1] = G[i][1];

    for (int j = 2; j <= m + 1; j++) {
        for (int i = 1; i <= n; i++) {
            dp[i][j] = dp[i][j - 1];
            if (i > 1)
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
            if (i < n)
                dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);
            dp[i][j] += G[i][j];
        }
    }

    ans = dp[b][m + 1];
    if (ans < h)
        printf("%d\n", h - ans);
    else
        printf("doctor win\n");

    return 0;
}