引用

官方C++题解

官方Java题解

题目描述

这一天你来到了蓝桥杯的考场,你发现考场是一个N*M的矩阵。
因为你的群友很多,你知道考场内每个人有多强,并且把实力换算成了数值。(因为有的人太弱了,所以可能出现实力值是负数的可能)
你想知道考场内实力总和最大的矩阵区域的实力和是多少。
注意:区域是按照矩形划分的

样例

输入格式

第一行两个整数 N M (1N×M2e5)\left(1\leq N \times M \leq 2e5\right)
第二到N+1行是一个N*M的矩阵代表考场内的情况 (200<=<=200)\left( -200<=实力值<=200 \right)

输出格式

请输出考场内实力总和最大的矩阵区域的实力和是多少

输入样例 1:

3 2
8 9
10 11
-4 11

输出样例 1:

45

输入样例 2:

3 2
8 9
10 11
-12 5

输出样例 2:

38

备注

对于10%数据 (1NM10)\left(1\leq N \leq M \leq 10\right)
对于40%数据 (1NM100)\left(1\leq N \leq M \leq 100\right)
对于70%数据 (1NM400)\left(1\leq N \leq M \leq 400\right)
对于100%数据 (1N×M2e5)\left(1\leq N \times M \leq 2e5\right)


算法

(二位前缀和) O(nm)O(nm)

从数据范围我们可以发现要是想拿满分朴素做法是不行的,即遍历所有子矩阵。这样的话时间复杂度是 O(n2m2)O(n^2m^2) , 铁定超时。还有不要直接开全局二维数组,这样会爆段错误,具体原因暂时不清楚。我们只需要根据输入的n,m来决定数组大小就行了。

对于新的做法可以看看这个题解AcWing126.最大的和,其实就是换了一种预处理前缀和的方法,通常我们都是算这个点左上角的数的和,但是现在我们只需要算每一列的和就行了,然后枚举的时候也不需要枚举左上角的点和右下角的点,只需要枚举上下界或者左右界,再枚举每一列或者每一行即可。这题也同样可以用贪心思想

因为数据范围的问题我们可以考虑翻转数组,如果行大于列,那么我们就翻转数组,这样我们遍历的行就会变少了,大大减少了复杂度,因为上下界循环次数是n!,虽然列的遍历也增多了,但是相对而言是影响不大的

时间复杂度 O(n)O(n)

预处理前缀和数组,所以计算的时候是 O(1)O(1)

C++ 代码

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    int n , m;
    LL ans = -0x3f3f3f3f;
    
    scanf("%d%d", &n, &m);
    
    int a[n + 1][m + 1];
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);
            
    if(n > m)
    {
        int b[m + 1][n + 1];
        // 复制数据
        for (int i = 1; i <= m; i ++ )
            for (int j = 1; j <= n; j ++ )
                b[i][j] = a[j][i];
        // 交换行列
        swap(n , m);
        // 预处理前缀和
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j++)
                b[i][j] += b[i - 1][j];
        // 枚举上下界
        for(int i = 1; i <= n; i ++)
        {
            for(int j = i; j <= n; j ++)
            {
                LL res = 0;
                for(int k = 1; k <= m; k ++)
                {
                    // 计算前k列的值,小于零就舍弃,大于就看看与ans谁大
                    res += b[j][k] - b[i - 1][k];
                    if(res < 0) res = 0;
                    if(res > ans) ans = res;   
                    // res = max(res , 0LL) + b[j][k] - b[i - 1][k];
                    // ans = max(res , ans);
                }
            }
        }
    }
    else
    {
        // 预处理前缀和
        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
                a[i][j] += a[i - 1][j];
        // 枚举上下界
        for(int i = 1; i <= n; i ++)
        {
            for(int j = i; j <= n; j ++)
            {
                LL res = 0;
                for(int k = 1; k <= m; k ++)
                {
                    // 计算前k列的值,小于零就舍弃,大于就看看与ans谁大
                    res += a[j][k] - a[i-1][k];
                    if(res < 0) res = 0;
                    if(res > ans) ans = res;
                    //res = max(res , 0LL) + a[j][k]-a[i-1][k];
				    //ans = max(ans , res);
                }
            }
        }
    }
    printf("%lld\n" , ans);
    
    return 0;
}