noi.ac 152 Christmas

提高组DP吧。

设$f(n,l,r)$表示从起点出发走到了第n列，并且在这一列的第l行到第r行可以自由走动的最小代价。

我们对于每一个l，按照从小到大的顺序枚举r，然后先计算出所有区间[l,r]的答案，然后再把一个区间的答案拿去更新它的子区间。

对于第n列的区间$[l,r]$，如果任意一个位置能被第n+1列的某个棋子控制，那么这个状态不合法。

同理如果这个区间不被任意一个第n-1列的棋子控制，那么$f(n,l,r)$的答案可以从$f(n-1,k,k)$，其中$k\in [l,r]$转移而来。

如果被至少一个棋子控制，那么设x为棋子行编号的最小值，y为棋子行标号的最大值，显然我们要保证第n-1列[x,y]之间的区域能自由走动，故可以从$f(n-1,x,y)$转移而来。

但是有一个特例，如果第n列区间$[l,r]$被第n-1列l-1行的棋子控制住，那么我们不能从$f(n-1,l-1,l-1)$转移而来（否则跳过了第n-1列第l行这个棋子，直接飞过来的?）,应该从$f(n-1,l-1,l)$转移而来。

计算完第n列所有区间的答案后，再跑一遍朴素区间DP，把大区间的答案传递给他所有的子区间即可。

边界条件：

初始时所有DP值为INF，$f(0,n,n)=0$。

#include <algorithm>
#include <cstring>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
// f(n,l,r) 前n列，让纵坐标区间[l,r]可自由走动的最小代价
int_t dp[1001][101][101];
int_t mat[101][1001];
int_t n, m;
const int_t INF = 0x7fffffff;
int main() {
    scanf("%lld%lld", &n, &m);
    for (int_t i = 1; i <= n; i++) {
        static char buf[10001];
        scanf("%s", buf + 1);
        for (int_t j = 1; j <= m; j++) {
            mat[i][j] = buf[j] - '0';
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    //当前位置左上是否有东西
    const auto blockByLeft = [&](int_t r, int_t c) {
        r -= 1, c -= 1;
        if (r >= 1 && r <= n && c >= 1 && c <= m) return (bool)mat[r][c];
        return false;
    };
    const auto blockByRight = [&](int_t r, int_t c) {
        r -= 1, c += 1;
        if (r >= 1 && r <= n && c >= 1 && c <= m) return (bool)mat[r][c];
        return false;
    };
    if (blockByRight(n, 1)) {
        cout << -1 << endl;
        return 0;
    }
    dp[0][n][n] = 0;
    for (int_t i = 1; i <= m; i++) {
        //枚举上端点
        for (int_t j = 1; j <= n; j++) {
            int_t sum = 0;
            //左侧列屏蔽当前点的最大最小行编号
            int_t minblock = INF, maxblock = 0;
            int_t minval = INF;
            bool hasblock = false;
            for (int_t k = j; k <= n; k++) {
                minval = std::min(minval, dp[i - 1][k][k]);
                if (blockByRight(k, i)) break;
                sum += mat[k][i];
                if (blockByLeft(k, i)) {
                    minblock = std::min(minblock, k - 1);
                    maxblock = std::max(maxblock, k - 1);
                    hasblock = true;
                }
                if (!hasblock) {
                    dp[i][j][k] = std::min(dp[i][j][k], minval + sum);
                } else {
                    dp[i][j][k] = std::min(
                        dp[i][j][k],
                        sum + dp[i - 1][minblock][std::max(j, maxblock)]);
                }
            }
        }
        //长度
        for (int_t j = n; j >= 1; j--) {
            //左端点
            for (int_t k = 1; j + k - 1 <= n; k++) {
                dp[i][k + 1][k + j - 1] =
                    std::min(dp[i][k + 1][k + j - 1], dp[i][k][k + j - 1]);
                dp[i][k][k + j - 2] =
                    std::min(dp[i][k][k + j - 2], dp[i][k][k + j - 1]);
            }
        }
    }
    int_t result = INF;
    for (int_t i = 1; i <= n; i++) {
        for (int_t j = i; j <= n; j++) {
            result = std::min(result, dp[m][i][j]);
        }
    }
    if (result > n * m) {
        result = -1;
    }
    cout << result << endl;

    return 0;
}