【题解】ybt1282：最大子矩阵

【题解】ybt1282：最大子矩阵

一本通是个好东西！不能好高骛远！！
有待思考的问题是能否把状态再压一维。

题目

【题目描述】

已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 × 1)子矩阵。

比如，如下4 × 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×NN×N的矩阵。输入的第一行给出N(0<N≤100)N(0<N≤100)。再后面的若干行中，依次(首先从左到右给出第一行的NN个整数，再从左到右给出第二行的NN个整数……)给出矩阵中的N2N2个整数，整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127][−127,127]。

【输出】

输出最大子矩阵的大小。

【输入样例】

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

【输出样例】

15

分析

暂时没有想到二维状态。本题解使用三维状态。

设(f[i][j][k])表示第(i)行中第(j)列到第(k)列的数字之和，直接累加即可。

设(c[i][j][k])表示以第(i)行第(j)列到第(k)列作为下底边的矩阵之和的最大值。

答案即为所有(c[i][j][k])里面的最大值。

先搞(f)，相当于处理线段，再搞(c)相当于处理面积。

(c)的转移:

c[i][j][k] = max(c[i][j][k], c[i - 1][j][k] + f[i][j][k]);

代码

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<bitset>
#include<set>
#include<map>
#define LL long long
using namespace std;
inline void Read(int &x){
	int f=1;
	char c=getchar();
	x=0;
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+c-'0';
		c=getchar();
	}
	x*=f;
}

int n, a[110][110], f[110][110][110], c[110][110][110], ans;
int main()
{
	ans = -0x3fffffff;
	Read(n);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)	Read(a[i][j]);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			for(int k = j; k <= n; ++k)
				f[i][j][k] = f[i][j][k - 1] + a[i][k];

	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
			for(int k = j; k <= n; ++k)
				c[i][j][k] = max(f[i][j][k], f[i][j][k] + c[i - 1][j][k]), ans = max(ans, c[i][j][k]);

	printf("%d
", ans);
	return 0;
}

谢谢游玩，希望能帮到你~