给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和最大。

其中,A的子矩阵指在A中行和列均连续的一块。

输入格式

输入的第一行包含两个整数n, m,分别表示矩阵A的行数和列数。接下来n行,每行m个整数,表示矩阵A。

输出格式

输出一行,包含一个整数,表示A中最大的子矩阵中的元素和。

输入样例:

3 3
-1 -4 3
3 4 -1
-5 -2 8

输出样例:

10

数据范围

对于5 对于10

题目分析

这道题,我们很明显能想出朴素的二维前缀和做法:

#include <iostream>
using namespace std;
using LL = long long;
const int N = 510;

int n, m, t;
LL g[N][N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) 
        for(int j = 1; j <= m; ++j) {
            cin >> g[i][j], g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];   
        }
    LL ans = 0;
    for(int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            for(int k = i; k <= n; ++k) {
                for(int l = j; l <= m; ++l) {
                    ans = max(ans, g[k][l] + g[i - 1][j - 1] - g[i - 1][l] - g[k][j - 1]);
                }
            }
        }
    }
    cout << ans;
    return 0;
}

但是交上会发现 TLE 了,我们考虑优化。

我们可以发现, 时间复杂度最高的地方就是我们比较计算最大子矩阵和的四重循环。

实际上, 我们可以通过设定子矩阵的一个上边界(行)、一个下边界(或者一个左边界、一个右边界, 那么之后应该移动下边界),再移动 右边界。 在移动 右边界 的过程中, 我们可以通过前缀和得到第 k 列的元素的和, 如果我们将每一列的和看作一个元素,那么原问题坍缩为一维问题:

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

我们考虑 DP : $$ f(i) = 结尾为\ nums[i]\ 时的连续子数组的最大和 $$ 我们很容易得到状态转移方程: $$ dp[i]=max(nums[i],dp[i−1]+nums[i]) $$

代码实现

#include <iostream>
using namespace std;
using LL = long long;
const int N = 510;

LL n, m, sum, ans, g[N][N];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> g[i][j], g[i][j] += g[i - 1][j];
    for(int i = 1; i <= n; ++i) {
        for(int j = i; j <= n; ++j) {
            ans = 0;
            for(int k = 1; k <= m; ++k) {
                ans += g[j][k] - g[i - 1][k];
                if(ans > sum || sum == 0) sum = ans;
                if(ans < 0) ans = 0;
            }
        }
    }
    cout << sum << "\n";
    return 0;
}
分类: DPPrefixSum

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status