【SSL 1056】最大子矩阵 (多维DP)

题目大意

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空（大小至少是$1\ast 1$）子矩阵。
比如，如下 $4\ast 4$ 子矩阵
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
的最大子矩阵是
9 2
-4 1
-1 8
这个子矩阵的大小是 $15$。

输入格式

输入一个 $N\ast N$$(1<=N<=500)$的整数矩阵，每个数的范围在 $-127$~$127$ 之间。

输出格式

输出最大子矩阵的大小。

输入样例

4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2

输出样例

15

基本思路

我们的第一想法肯定是暴力枚举，但即便用二维前缀和优化依然是 $O(n^4)$ ，明显是承受不了的。我们观察数据规模可以发现 $O(n^3)$ 是可以承受的，因为每个 $for$ 循环不一定都是 $n$ ，那么怎么优化呢？

首先我们可以枚举枚子矩阵的宽度，即它有多少列。然后我们在将这个子矩阵中每一行的数加起来看成一个数。

此时我们得到了一个从上到下有 $n$ 个数的数列（因为我们只枚举了宽度，长度即行数则默认为 $n$）。接下来就要确定行数了，现在问题就转化为在这 $n$ 个数中选取一段和最大的连续子序列。 在这个图中就是 $11,-3,7$，由此确定的子矩阵为 { 9 , 2 } \{9,2\} {9,2} { − 4 , 1 } \{-4,1\} {−4,1} { − 1 , 8 } \{-1,8\} {−1,8} 了。

还有一个问题需要注意，因为存在负值情况，所以 $ans$ 要赋一个极小值。

核心代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=510;
int n,s[N][N],ans=-1e9;
int main(){ios::sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){cin>>s[i][j];s[i][j]+=s[i][j-1];}for(int d=0;d<n;d++){//枚举宽度 for(int i=1;i+d<=n;i++){int j=i+d,tmp=0;for(int k=1;k<=n;k++){tmp+=(s[k][j]-s[k][i-1]);//将此行的数看成一个数ans=max(ans,tmp);tmp=max(tmp,0); }}}cout<<ans;
//	2
//	-4 -2
//	-3 -1
//	
//	-1return 0;
}