Blackops

初心易得，始终难守

0%

NYOJ 104 最大和（最大子矩阵经典问题）

发表于 分类于 ，

最大和
时间限制：1000 ms | 内存限制：65535 KB
难度：5

描述
给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。
例子：
\begin{array}{c|lcr}
&0 &-2 &-7 &0 \
&9 &2 &-6 &2 \
&-4 &1 &-4 &1 \
&-1 &8 &0 &-2 \
\end{array}
其最大子矩阵为：
\begin{array}{c|lcr}
&9 &2 \
&-4 &1 \
&-1 &8 \
\end{array}
其元素总和为15。

输入
第一行输入一个整数n（0<n<=100）,表示有n组测试数据；
每组测试数据：
第一行有两个的整数r，c（0<r,c<=100），r、c分别代表矩阵的行和列；
随后有r行，每行有c个整数；
输出
输出矩阵的最大子矩阵的元素之和。
样例输入
1
4 4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
样例输出
15

题目链接：NYOJ 104
首先这题很容易想到作一遍二维前缀和，然后枚举对角线差分更新答案，显然复杂度是$O(n^4)$的，实际上我们可以用另外的方法做，考虑答案的矩阵肯定是一个连续的列向量构成，那么我们可以枚举这个列向量的顶端和底端，将每一个列向量压缩求和成一项，然后再对$m$个列向量的和做一遍$(n)$的$DP$，那么复杂度就变成$O(n^3)$了，最后似乎子矩阵不能为空，因此如果都是负数就输出一个最大的负数。
代码：

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <bitset>
#include <string>
#include <stack>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 110;
int G[N][N], arr[N], dp[N], colsum[N][N];
int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
inline int solve(int a[], int l, int r)
{
    dp[l - 1] = -INF;
    for (int i = l; i <= r; ++i)
        dp[i] = max(dp[i - 1] + a[i], a[i]);
    return *max_element(dp + l, dp + r + 1);
}
int main(void)
{
    int TC, n, m, i, j;
    TC = read();
    while (TC--)
    {
        n = read();
        m = read();
        for (i = 1; i <= n; ++i)
            for (j = 1; j <= m; ++j)
                G[i][j] = read();
        for (j = 1; j <= m; ++j)
            for (i = 1; i <= n; ++i)
                colsum[i][j] = colsum[i - 1][j] + G[i][j];//用于差分求列和的前缀数组
        int ans = -INF;
        for (i = 1; i <= n; ++i)
        {
            for (j = i; j <= n; ++j)
            {
                for (int k = 1; k <= m; ++k)//压缩的和放到arr数组里
                {
                    arr[k] = colsum[j][k] - colsum[i - 1][k];
                }
                ans = max(ans, solve(arr, 1, m));//对arr做一遍dp
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}