题解：CF812B Sagheer, the Hausmeister

Blikewsr

2024-11-18 20:09:49

Solution

题目传送门

CF812B - Luogu

CF812B - Codeforces

题目简述

给定一个楼层图，用 01 表示，1 表示开灯的房间，最左边和最右边为楼梯间，用 0 表示，我们在 最底层最左边 的楼梯口，求至少要走多少步才能关掉所有的灯。

思路分析

注意到，最高几层可能全部是 0，说明这几层没有灯，我们跟本不用走，所以我们可以先枚举每一层，找到 最高的且有灯开着的 一层开始走。

我们定义一个二维数组 cnt[N][2]，其中 cnt_{i, 0} 表示从第 i 层楼 左边 进入的情况下，关掉第 i 层及其楼上所有层的灯的 最小步数，cnt_{i, 1} 表示从第 i 层楼 右边 进入的情况下，关掉第 i 层及其楼上所有层的灯的 最小步数。

然后在定义一个两个一维数组 lef[N] 和 rig[N]，其中 lef_i 表示第 i 层楼 最左边亮着灯 的房间号，rig_i 表示第 i 层楼 最右边亮着灯 的房间号

现在，我们来考虑以下转移方程。

显然的，每一层的步数只受它上一层的步数和本层亮灯的房间影响的。

其次，最优的走法肯定是要么走完一整层从另一边上到上一层，要么走到这一层里所在楼梯口最远的亮着灯的房间在原路返回在上到上一层，所以我们有 4 种走发：

  1. 从第 i 层 左边 进入，右边 上楼。
  2. 从第 i 层 左边 进入，左边 上楼。
  3. 从第 i 层 右边 进入，左边 上楼。
  4. 从第 i 层 右边 进入，右边 上楼。

对于第 1 种走法，我们可以得到：

cnt_{i, 0} = cnt_{i + 1, 1} + (m + 1) + 1

对于第 2 种走法，我们可以得到：

cnt_{i, 0} = cnt_{i + 1, 0} + rig_i \times 2 + 1

对于第 3 种走法，我们可以得到：

cnt_{i, 1} = cnt_{i + 1, 0} + (m + 1) + 1

对于第 4 种走法，我们可以得到：

cnt_{i, 1} = cnt_{i + 1, 1} + (m - (lef_i - 1)) \times 2 = cnt_{i + 1, 1} + (m - lef_i + 1) \times 2 + 1

知道了所有的走法的转移方程，既然我们要求最小步数，那么我们直接让对应的转移方程分别取最小值就可以了。

即：

cnt_{i, 0} = \min(cnt_{i + 1, 0} + rig_i \times 2, cnt_{i + 1, 0} + rig_i \times 2) + 1 cnt_{i, 1} = \min(cnt_{i + 1, 0} + (m + 1), cnt_{i + 1, 1} + (m - lef_i + 1) \times 2) + 1

注意： 转移方程上面的加一是因为上楼区要在楼梯间走一步，所以 最高的且有灯开着的 那一层楼不用上楼。

其他细节见代码注释

代码实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, h, mp[20][107], lef[20], rig[20];
int cnt[20][2];
char s[20][107]; 
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        cin >> s[i]; // 因为输入没有空格，先用字符类型输入
    for (int i = 1; i <= n; ++ i) {
        lef[i] = m + 1, rig[i] = 0;
        for (int j = 1; j <= m; ++ j) {
            mp[i][j] = (int)(s[i][j] - '0');
            if (mp[i][j]) {
                if (lef[i] == m + 1) lef[i] = rig[i] = j; // 最左边亮着灯的房间
                else rig[i] = j; // 最右边亮着灯的房间
                if (!h) h = i; // 最高的且有灯开着的一层
            }
        }
    }
    if (!h) { // 整个楼房没有房间开灯，直接走人
        cout << "0\n";
        return 0;
    }
    cnt[h][0] = rig[h], cnt[h][1] = m - lef[h] + 1;
    for (int i = h + 1; i <= n; ++ i) {
        // 转移方程
        cnt[i][0] = min(cnt[i - 1][0] + rig[i] * 2, cnt[i - 1][1] + m + 1);  
        cnt[i][1] = min(cnt[i - 1][1] + (m - lef[i] + 1) * 2, cnt[i - 1][0] + m + 1);
        // 往上走一层
        ++ cnt[i][0];
        ++ cnt[i][1];
    }
    cout << cnt[n][0] << '\n'; // 因为在左侧，所以输出 cnt[n][0]
    return 0;
}

提交记录