蒟蒻在DP之路上求索着

题目:传送门

题目描述

回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中,然后开始思考:到底要以何种方法吃鱼呢(猫猫就是这么可爱,吃鱼也要想好吃法 ^_*)。她发现,把大池子视为01矩阵(0表示对应位置无鱼,1表示对应位置有鱼)有助于决定吃鱼策略。

在代表池子的01矩阵中,有很多的正方形子矩阵,如果某个正方形子矩阵的某条对角线上都有鱼,且此正方形子矩阵的其他地方无鱼,猫猫就可以从这个正方形子矩阵“对角线的一端”下口,只一吸,就能把对角线上的那一队鲜鱼吸入口中。

猫猫是个贪婪的家伙,所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下,她一口下去,最多可以吃掉多少条鱼?

数据范围

对于所有数据,$n,m\le 2500$

题解

这道题的要求非常特殊,是要求出最大的满足”只有对角线上全是1,其他部分都是0”的最大的正方形.与[ZJOI2007]棋盘制作类似.通常这种矩阵类的DP,我们都会设$f[i][j]$表示在某个坐标时的状态.然而这题有一个问题,那就是每当我们进行一行或者一列,我们都要求:除了$(i,j)$外该行/列都是0.这不是一个直接就能求出来的量.但是我们发现由于一次只会推进一格,我们可以初始化这个量.

先求左上-右下对角线的值.我们设$l[i][j]$表示从$(i,j)$往左最长连续多少个0,设$u[i][j]$表示从$(i,j)$向上最长连续多少个0.这样我们在更新状态的时候就可以使用现成的信息了.

然后就是状态.设$f[i][j]$表示以点$(i,j)$为右下角的最大的满足题意的正方形的边长.因为边长和主对角线的格数是一样的.根据题意,很显然的一点是,只有$b[i][j]$(b数组表示池塘)为1的时候才有答案.那么我们怎么转移呢?题目中要求的是正方形,所以如果向上延申的0的个数<向左的,那显然只能按照小的那个来(木桶效应).其次我们还要考虑是从什么状态转移过来的.显然是从左上方延长对角线来的.所以我们要从三者中取最小的(同样是因为木桶效应).也就是:
$$
f[i][j]=min(f[i-1][j-1], min(l[i][j],u[i][j]))+1
$$
这就是左上-右下对角线的求法.对于右上-左下对角线我们只需要从右上角开始预处理一个r数组,其他的类似即可.

代码:

int b[N][N], n, m, l[N][N], u[N][N], r[N][N], f[N][N], ans;

int main() {
    read(n), read(m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            read(b[i][j]);//读入
    for (int i = 1; i <= n; ++i)
        b[i][0] = 1, b[i][m + 1] = 1;//为了防止多记录0的数量,把边界标记为1
    for (int j = 1; j <= m; ++j)
        b[0][j] = 1, b[n + 1][j] = 1;
    for (int i = 1; i <= n; ++i) {//处理l数组和u数组
        for (int j = 1; j <= m; ++j) {
            if (b[i - 1][j] == 0)
                u[i][j] = u[i - 1][j] + 1;
            if (b[i][j - 1] == 0)
                l[i][j] = l[i][j - 1] + 1;
        }
    }
    for (int i = 1; i <= n; ++i)//因为顺序原因单独处理r数组
        for (int j = m; j >= 1; --j)
            if (b[i][j + 1] == 0)
                r[i][j] = r[i][j + 1] + 1;
    for (int i = 1; i <= n; ++i) {//状态转移
        for (int j = 1; j <= m; ++j) {
            if (b[i][j] != 1) continue;//判断当前位置是否合法
            f[i][j] = 1;
            if (b[i - 1][j - 1] != 1) continue;
            f[i][j] = min(f[i - 1][j - 1], min(l[i][j], u[i][j])) + 1;
            ans = max(ans, f[i][j]);
        }
    }
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {//处理右上-左下对角线
        for (int j = m; j >= 1; --j) {
            if (b[i][j] != 1) continue;
            f[i][j] = 1;
            if (b[i - 1][j + 1] != 1) continue;
            f[i][j] = min(f[i - 1][j + 1], min(r[i][j], u[i][j])) + 1;
            ans = max(ans, f[i][j]);//两种答案取较大值
        }
    }
    cout << ans << endl;
    return 0;
}

——Gensokyo