难度：提高+/省选-

题目描述

        回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考:到底要以何种方法吃鱼呢(猫猫就是这么可爱，吃鱼也要想好吃法 ^_*)。她发现，把大池子视为01矩阵(0表示对应位置无鱼，1表示对应位置有鱼)有助于决定吃鱼策略。
        在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。
        猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？

输入输出格式

输入格式:

        有多组输入数据，每组数据:
        第一行有两个整数n和m(n，m≥1)，描述池塘规模。接下来的n行，每行有m个数字(非“0”即“1”)。每两个数字之间用空格隔开。
        对于30%的数据，有n，m≤100
        对于60%的数据，有n，m≤1000
        对于100%的数据，有n，m≤2500

输出格式:

        只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。

输入输出样例

Sample input

4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0

Sample output

3

题解

        考察二维DP。该题目与本材料第一题最大正方形有类似之处。
        容易发现，从左下角开始向右上方吸和从右上角开始向左下方吸本质是一样的。不妨强制要求只能向上吸，这样吸的方向就只有两种:向左上方和向右上方。
        规定dp(x，y，z)为从坐标(x，y)开始向z方向吸到的鱼的最大数目。这里z的定义是:向左上方为0，向右上方为1。dp全初始化为0。
        但是这样很难进行状态转移，这是因为在方阵中只有对角线有鱼时才可以吸。如果没有这个限制，状态转移方程很容易列出。
        由于加上了限制，需要三个辅助数组来帮助完成状态转移。
        取R1(x，y)表示坐标(x，y)的左方离它最近的鱼与其的距离;R2(x，y)表示坐标(x，y)的右方离它最近的鱼与其的距离;C(x，y)表示坐标(x，y)的上方离它最近的鱼与其的距离。不需要与下方鱼的距离，这是因为已经强制规定只能向上吸，下方的鱼对求解没有意义。这里的三个数组都在坐标(x，y)有鱼时才有定义。在某个方向上没有鱼时，直接赋上与边界的距离即可。
        这样的话，状态转移方程就可以列出了，在坐标(x，y)有鱼时，有如下递推式:

        坐标(x，y)没有鱼时，直接赋值为0。
        从所有dp值中找到最大值即为答案。
        示例代码的数组记录的是鱼的坐标值，在递推时现算出距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>

using namespace std;
int dp[2505][2505][2] = {0};
int n, m;
short int op[2501][2501] = {0};
short int sumR_1[2505][2505] = {0};
short int sumR_2[2505][2505] = {0};
short int sumC[2505][2505] = {0};

int main() {
    cin >> n >> m;
    for (register int i = 1; i <= n; i++) {
        int temp = 0;
        for (register int j = 1; j <= m; j++) {
            cin >> op[i][j];
            if (op[i][j])sumR_2[i][temp] = j, sumR_1[i][j] = temp, temp = j;
        }
        sumR_2[i][temp] = 2501;
    }
    for (register int i = 1; i <= m; i++) {
        int temp = 0;
        for (register int j = 1; j <= n; j++)
            if (op[j][i])sumC[i][j] = temp, temp = j;
    }
    int ans = 0;
    for (register int i = 1; i <= n; i++) {
        for (register int j = 1; j <= m; j++) {
            if (!op[i][j])continue;
            dp[i][j][0] = min(min(j - sumR_1[i][j], i - sumC[j][i]), 
dp[i - 1][j - 1][0] + 1);
            dp[i][j][1] = min(min(sumR_2[i][j] - j, i - sumC[j][i]), 
dp[i - 1][j + 1][1] + 1);
            ans = max(ans, max(dp[i][j][0], dp[i][j][1]));
        }
    }
    cout << ans << endl;
    return 0;
}