思路与算法

自底向上处理每一行。令 below[c] 表示从下一行第 $c$ 列开始的最优剩余罚分，包括那个格子的费用。当前行已付过当前位置的费用。

关键化简是：对正在处理的一行，Bob只需把已经放弃的向下出口封成连续区间。Alice在区间的一个端点。Bob可以保留当前向下出口并封住其他出口，迫使从当前列下降，代价为 below[c]；也可以封住当前出口，迫使Alice走到区间左侧或右侧的新出口。Alice会选择较便宜的一边。横向来回走不会改变观察到的出口，也不会减少非负费用，因此可直接用前缀和结算两端之间的行走费用。

令 $f[l][r][s]$ 表示已经到达区间 $[l,r]$，当前位置是左端（$s=0$）或右端（$s=1$），当前格费用已付，区间内其余向下出口已封时的最优后续费用。若区间覆盖全行，Bob不能再封最后的出口，必须向下。否则令 $E$ 为Alice向左扩大或向右扩大区间的较小代价，则 $f=\max(\text{below}[c],E)$。按区间长度从大到小计算。当前行起点列 $c$ 的值是 $a_{row,c}+f[c][c][0]$。最后一行直接取格子费用，第一行取所有起点的最小值。

正确性说明

先说明行模型：水平边不能封，故同一行任一尚开放的向下出口均可经水平移动到达。对Alice而言，离开已到达的连续区间只能从其两端发生；区间内部绕行增加非负费用而不提供新出口。对Bob而言，提前封掉区间外尚未到达的出口不会创造新的选项，可延迟到Alice到达该出口时决定。Bob若决定在当前列下降，可以同时封掉其余出口；这使Alice不能通过改选其他列获得更低后续代价。

若Alice已经下降，返回上一行不会提供更优的保证：Bob可以把刚经过的向上边封掉，而下一行始终有水平通路通向尚未封死的下方出口，故这种封边合法。对Alice的上界策略也不需要向上回返。因此两人最优值可用逐行过程表达。

在区间状态中，Bob保留当前出口并封其他出口时可以强制取得 below[c]；封当前出口时，Alice只能选择下一次首次离开区间的左侧或右侧，由最优选择给出 $E$。这两类覆盖Bob的有效策略，故取最大值。全行状态只剩当前位置的出口，继续封会断开与末行的连通，因而必须下降。转移总依赖更长区间，区间归纳成立；从末行向上归纳即得全局最优值。

复杂度

每行有 $O(m^2)$ 个两端区间和两个端点状态，每个状态只比较两个扩张方向，前缀和结算费用为 $O(1)$。包括读入和末行初始化，总时间 $O(Tnm^2)$，空间 $O(nm+m^2)$；每行前缀和初始化 $O(m)$ 已计入。最多 $T=10,n=m=100$，使用64位整数保存罚分。

易错点

起点和每次进入的格子都收费，状态中当前位置已经付费，扩张时不要重复计当前位置。最后一行到达即结束，不再横向走。全行状态不能继续封最后一个出口。费用可能为0，不能用“无限走动的零费用回路”替代合法终止策略。$n=1$ 取首行最小值，$m=1$ 必须沿唯一列向下。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc;
    cin >> tc;
    while (tc--) {
        int n, m;
        cin >> n >> m;
        vector<vector<ll>> a(n, vector<ll>(m));
        for (auto &r : a)
            for (auto &x : r)
                cin >> x;
        vector<ll> below(m);
        for (int row = n - 1; row >= 0; --row) {
            if (row == n - 1) {
                below = a[row];
                continue;
            }
            vector<ll> pref(m + 1);
            for (int j = 0; j < m; ++j)
                pref[j + 1] = pref[j] + a[row][j];
            vector<vector<array<ll, 2>>> f(m, vector<array<ll, 2>>(m));
            for (int len = m; len >= 1; --len)
                for (int l = 0; l + len <= m; ++l) {
                    int r = l + len - 1;
                    for (int side = 0; side < 2; ++side) {
                        int at = side ? r : l;
                        ll expand = LLONG_MAX / 4;
                        if (l > 0)
                            expand = min(expand, pref[at] - pref[l - 1] + f[l - 1][r][0]);
                        if (r + 1 < m)
                            expand = min(expand, pref[r + 2] - pref[at + 1] + f[l][r + 1][1]);
                        f[l][r][side] = len == m ? below[at] : max(below[at], expand);
                    }
                }
            for (int j = 0; j < m; ++j)
                below[j] = a[row][j] + f[j][j][0];
        }
        cout << *min_element(below.begin(), below.end()) << '\n';
    }
}