信息学奥赛一本通（1224：最大子矩阵）

1224：最大子矩阵

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 5292     通过数: 3128

【题目描述】

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

【输入】

输入是一个N×N的矩阵。输入的第一行给出N(0

【输出】

输出最大子矩阵的大小。

【输入样例】

40 -2 -7 09 2 -6 2 -4 1 -4 1 -1 8 0 -2

【输出样例】

15

【分析】

        这道题的解法有前缀法和动态规划法，贪心算法解法暂时还没有想到，下面来讲解一下前缀法。

        前缀和是一个数组的某项下标之前(包括此项元素)的所有数组元素的和。设a为原数组，b为前缀和数组。

        一维数组前缀和定义为：，二维数组前缀和定义为：，以样例为例，原矩阵a为：

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

则，前缀和矩阵b为：

0 -2 -9 -9
9 9 -4 -2
5 6 -11 -8
4 13 -4 -3

        递推公式为：b[x][y]=b[x-1][y]+b[x][y-1]-b[x-1][y-1]+a[i][j]。这个递推公式也不难理解，就是容斥原理。比如，上面b数组的第4行第2列数据13，套用上述公式，其值就是：13 = 6 + 4 - 5 + 8。

        回到本题，假设求下列原矩阵红框部分子矩阵的和，肉眼可见，下图子矩阵和 = -7。

        用前缀和矩阵求解方式为：-11 - （-9）- 5 + （-4） = -7。

        这里给出O(n^4)的代码，O(n^3)的解法参见后续的1282题目。

        四重循环，设子矩阵左上角坐标为(k,l)，右下角(i,j)。则分别枚举 i，j，k，l 即可，枚举范围 i∈[1,n]，j∈[1,n]，k∈[1,i ]，l∈[1,j ]。

【参考代码】

#include <stdio.h> #define N 110 int a[N][N]; int sums[N][N]; int main() {int i,j,k,l,n,t,max;scanf("%d",&n);for(i=1;i<=n;i++) //前缀和 {for(j=1;j<=n;j++){scanf("%d",&a[i][j]);sums[i][j]=sums[i-1][j]+sums[i][j-1]-sums[i-1][j-1]+a[i][j];}}max=sums[1][1];for(i=1;i<=n;i++){for(j=1;j<=n;j++){for(k=1;k<=i;k++) //枚举每个子矩阵，左上角(k,1)，右下角(i,j)，子矩阵和 {for(l=1;l<=j;l++){t=sums[i][j]-sums[i][l-1]-sums[k-1][j]+sums[k-1][l-1];if(t>max)max=t;}}}}printf("%d\n",max);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1224

总结

以上是生活随笔为你收集整理的信息学奥赛一本通（1224：最大子矩阵）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。