POJ1050-To The Max

2022-03-04 题解

题目大意：给出一个方阵，元素有正有负，问这个方阵的子矩阵中，所有元素之和最大能取到多少。

求一个矩阵的子矩阵元素和，第一反应就是二维前缀和。令s[x][y]为所有s[i][j],1<=i<=x,1<=j<=y之和，那么左上角元素为a[x1+1][y1+1]，右下角元素为a[x2][y2]的所有元素之和就是

1	s[x2][y2] - (s[x1][y2] + s[x2][y1] - s[x1][y1])

如果是求一个一维序列的最大子串值，只需要扫描一遍前缀和数组s，并且扫描的过程中记录下已经扫描的部分中前缀和的最小值，每次用扫描到的前缀和数组元素减去这个最小值的结果来更新最大的子串值即可。但是在二维前缀和中，求和所需要减去的变量有多个参数，不能只简单地记下一个值了事。

如果是记下s[x2][y] (y<=y2)，和s[x][y2] (x<=x2)的最小值（假设为s[x2][miny]和s[minx][y]），并直接令y1=miny, x1=minx是否可行？答案是否定的。因为计算中减去的式子不仅包括s[x1][y2] + s[x2][y1]，还包括- s[x1-1][y1]。

正如下面这组数据

显然，最大子矩阵是左下角的方阵（最大值为10），但当x2=3,y2=2时，如果按照上面的取法，miny[x2]的值为1，minx[y2]的值为1，即取得的x1=y1=2。但显然，x1为0时所能取得的值更大。

考虑换一种做法：如果已经确定了x1，即左上角的点所在行数，并且记录下了在这一行中取得最小值的点，就又可以知道y1的值了。所以，对于每个点上方的每一行，用已经记录的，每一行中能取得的最优点，将它作为左上角的点来更新答案即可。这么做的复杂度是 $O(n^3)$ ，在可以接受的范围内。

#include <bits/stdc++.h>
using namespace std;
int a[505][505], s[505][505];
int minj[505]; // minj[i][j]:在第i行的点中，所能取得的最优点的列号
int main()
{
    int n, i, j, k, res = 0;
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            scanf("%d", &a[i][j]);
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 1; j <= n; j++)
            s[i][j] = a[i][j] + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    }
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j <= n; j++)
            minj[j] = 0;
        for (j = 1; j <= n; j++)
        {
            for (k = 0; k < i; k++)
            {
                res = max(res, s[i][j] - s[i][minj[k]] - s[k][j] + s[k][minj[k]]);
                if (s[i][j] - s[k][j] < s[i][minj[k]] - s[k][minj[k]])
                    minj[k] = j;
            }
        }
    }
    printf("%d", res);
    return 0;
}