原题链接或者这个

1 题目

1.1 题目所需求出内容

对于本题，最终要求：最大值

1.2 题目背景、允许、禁止与限制

背景：有一个大小为 $n \times m$ 的只含 $0,1$ 两种数字的矩形。$0$ 表示无鱼，$1$ 表示有鱼
允许：选择一个矩形中的正方形子矩阵，从这个子矩阵的对角线的一端“吸一下”，就可以收获这条对角线上的所有鱼
禁止：
限制：选择出的正方形子矩阵只允许在吸的那条上全是鱼，其他地方不能有一点鱼

1.3 题目数据范围与猜测

$1 \le n,m \le 2500 \longrightarrow O(nm)$

1.4 一句话概括题意

在一个矩形中选择一个正方形子矩阵，从矩阵的对角线一端进行一次吸的操作，要求吸时满足：

• 吸的这条对角线必须全部都有鱼
• 吸的这个对角线对应的正方形子矩阵除了对角线以外其他地方都不是鱼

2 题目破题推导

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 以终为始、以始为终

2.4 数学

2.5 分情况考虑

分两种情况考虑：

• 第一种：如果当前这个位置没有鱼，那么不可能从这里吸到任意哪怕一条鱼
• 第二种：如果当前这个位置有鱼，那么就需要记录从这个点往左/右上角吸可以吸到的最多鱼，还要判断如果这个矩阵内的数字总和 $>$ 可以吸到的最多鱼，说明这个位置往左/右上角吸到某个位置会出现正方形子矩阵其他地方有鱼的情况。而直到某一位不存在这样的状况，则代表可以吸完这个对角线上的鱼。
• • 有些人可能会有疑问，为什么只需要记录“往左/右上角延伸”？
• • 因为“往左下角/右下角延伸”已经被刚刚的那种答案所包含

2.6 手动推导

2.7 边界测试

3 模型匹配

先提取关键词：时刻求取当前最大值、只和特定的几位有关系
那不用说了，一定是 $\huge{动态规划}$
但是这题还有两个问题，咱们一会再说

4 具体方案

4.1 动态规划定义（重点）

首先，建立两个dp 数组，姑且先叫它们dpl 和 dpr
设置 ${dpl_i}_j$ 表示以 $(i,j)$ 为右下角时，往左上角延伸可以获得的最大鱼数
再设置 ${dpr_i}_j$ 表示以 $(i,j)$ 为左下角时，往右上角延伸可以获得的最大鱼数

4.2 初始化

求最大值，所以dpl和dpr数组每一项都设为小值

4.3 状态转移方程

这里有两个地方需要注意

4.3.1 遍历顺序

dpl的遍历顺序非常明了，$i$ 从 $1$ 到 $n$，$j$ 从 $1$ 到 $m$
但是对于dpr的定义来说，我们一定要先计算右上角的值才能通过前面求得的结果求解后面的元素
因此dpr的遍历顺序是$i$ 从 $1$ 到 $n$，$j$ 从 $m$ 到 $1$

4.3.2 无鱼的处理

我们前面说过，当 ${a_i}_j=0$ 时，说明这个位置没有鱼，那此时 ${dp_i}_j$ 应该赋值为 $0$

4.3.3 代码

for (int i = 1;i <= n;i++){
    for (int j = 1;j <= m;j++){
        if (a[i][j] == 0){
            dpl[i][j] = 0;
            continue;
        }
        dpl[i][j] = dpl[i - 1][j - 1] + a[i][j];
    }
}
for (int i = 1;i <= n;i++){
    for (int j = m;j >= 1;j--){
        if (a[i][j] == 0){
            dpr[i][j] = 0;
            continue;
        }
        dpr[i][j] = dpr[i - 1][j + 1] + a[i][j];
    }
}

4.4 答案求取

这里有很多地方需要注意

4.4.1 哪些地方是合理的

我们只先探讨dpl的，dpr的请大家自行脑补
因为我们之前说过，当且仅当这个正方形子矩阵只有一条对角线上全是鱼时
那我们可以记录一下每个正方形子矩阵的总和（相当于这个正方形子矩阵中有多少鱼）
真正的答案 $k$ 从 ${dpl_i}_j$ 到 $1$，直到某一位对应的正方形子矩阵总和 $=k$，说明这个答案是合法的
如果真的是这样，时间复杂度大家想象一下大约是 $O(n^3m^2)$

4.4.1.1 优化

• 第一个是查询“正方形子矩阵的总和”
  不难想到，这就是一个二维前缀和模板
• 第二个是遍历真正的答案 $k$
  我们想一下，这个 $k$ 作为答案时一定是具有单调性的，因此就考虑二分查找

最终能优化成 $O((nm)log k)$

4.4.2 最终答案到底是哪些项

是我们把所有dpl和dpr的 $k$ 都处理完之后的最大值

5 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 定义
int n, m;
const int N = 2555;
int a[N][N];
int dpl[N][N];
int dpr[N][N];
ll sum[N][N];
// 二维前缀和相关函数
void pre_sum(){
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
}
inline ll query(int xs, int ys, int xe, int ye){
    return sum[xe][ye] - sum[xs - 1][ye] - sum[xe][ys - 1] + sum[xs - 1][ys - 1];
}

int main(){

    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            cin >> a[i][j];
        }
    }
    pre_sum();
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            if (a[i][j] == 0){
                dpl[i][j] = 0;
                continue;
            }
            dpl[i][j] = dpl[i - 1][j - 1] + a[i][j];
        }
    }
    for (int i = 1;i <= n;i++){
        for (int j = m;j >= 1;j--){
            if (a[i][j] == 0){
                dpr[i][j] = 0;
                continue;
            }
            dpr[i][j] = dpr[i - 1][j + 1] + a[i][j];
        }
    }
    int left_mx = 0;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= m;j++){
            int mx_len = dpl[i][j];
            int l = 1, r = mx_len;
            while(l <= r){
                int mid = (l + r) / 2;
                ll ps = query(i - mid + 1, j - mid + 1, i, j);
                if (ps == mid){
                    left_mx = max(left_mx, mid);
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
    }
    int right_mx = 0;
    for (int i = 1;i <= n;i++){
        for (int j = m;j >= 1;j--){
            int mx_len = dpr[i][j];
            int l = 1, r = mx_len;
            while(l <= r){
                int mid = (l + r) / 2;
                ll ps = query(i - mid + 1, j, i, j + mid - 1);
                if (ps == mid){
                    right_mx = max(right_mx, mid);
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
    }
    cout << max(left_mx, right_mx);
    
    return 0;
}