CodeForces – 812B Sagheer, the Hausmeister 搜索 dp

题意：给你n行长度为m的01串（n<15,m<100) 。每次只能走一步，要将所有的1变为零，问最少的步数，注意从左下角开始，每次要将一层清完才能走到上一层，每次只有在第一列或者最后一列才能往上走一层，否则只能左右移动。

题解：由于清完当前层才能继续上一层，所以必然存在一个递推关系。先递推预处理，然后输出ans即可。用far来存最远的那个1，如果这层没有1，假设有一个，令其距离为1

具体看代码注释吧。

坑：没考虑没有1以及只有1层的情况

#define  _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + ;
int m, n, len;
int dp[][];//清完i层回到最左0右1 所需的min
int far[][];//每层楼离左0右1 最远的灯
int no[];
int main() {
    while (cin >> n >> m) {
        for (int i = ; i <= n; i++) {//从顶层开始输入
            string s;
            cin >> s;
            len = s.length();
            int j;
            int ok = ;
            for (j = ; j < len - ; j++) if (s[j] == '') { far[n +  - i][] = len - j; break; }            for (j = len - ; j > ; j--)if (s[j] == '') { far[n +  - i][] = j + ; break; }
            for (j = ; j < len; j++) { if (s[j] == '') ok = ; }
            if (ok == )far[n +  - i][] = , far[n +  - i][] = , no[n +  - i] = ;
        }
        //如果某层没灯+1跳过：
        if (no[]) far[][] = ;//floor 1 no lamp
        dp[][] = len - ; dp[][] = far[][] *  - ;//wa这儿了，忘记考虑只有1层，应该改far
        for (int i = ; i <= n; i++) {
            for (int j = ; j <= ; j++)dp[i][j] = maxn;
            dp[i][] = min(max(, dp[i - ][] + far[i][] *  - ), dp[i - ][] + len);
            dp[i][] = min(max(, dp[i - ][] + far[i][] *  - ), dp[i - ][] + len);
        }        //1st floor start from left,
        int k = n;
        while (no[k])k--;        int ans = min(dp[k - ][] + far[k][], dp[k - ][] + far[k][]);
        //1层
        if (k == ) {
            far[][]--; ans = far[][];
        }
        cout << ans << endl;
    }
    cin >> n;
}