To the Max poj-1050
题目大意：给你一个n*n的矩阵，求最大子矩阵的和。每一个数不一定是正数。
注释：n<=100.
想法：以前听学长讲过bz的玉蟾宫，好像这题可以$n^3$。我在此介绍$n^3$的做法。这其实是一种扩展：首先，我们会O(n)的求一串数的最大连续字段和。我们想，如何才能处理出矩阵层面的最大子矩阵呢？我们想，我既然会求一串数的最大连续字段和，那么我们就可以将这个过程进行拓展，我们可以求出任意两行之间的最大子矩阵，这个子矩阵的上下两条边分别在这两行上。这样的话我们怎么处理，比如说我们枚举到了i行到j行，那么，我们对于每一列的元素，就可以将每一列的元素相加成一个，然后用O(n)的算法求出最大子矩阵，然后维护前缀和，before[i][j]表示for(int k=1;k<=i;k++) ans+=a[k][j]，即可。
最后，附上丑陋的代码... ...
1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4 int a[110][110]; 5 int before[110][110]; 6 int main() 7 { 8 int n; 9 scanf("%d",&n); 10 for(int i=1;i<=n;i++) 11 { 12 for(int j=1;j<=n;j++) 13 { 14 scanf("%d",&a[i][j]); 15 } 16 } 17 for(int i=1;i<=n;i++) 18 { 19 for(int j=1;j<=n;j++) 20 { 21 before[i][j]=before[i-1][j]+a[i][j]; 22 } 23 } 24 int maxmid=0xefefefef; 25 int maxbefore=0xefefefef; 26 int maxall=0xefefefef; 27 for(int i=1;i<=n;i++) 28 { 29 for(int j=i;j<=n;j++) 30 { 31 maxbefore=0; 32 maxmid=0xefefefef; 33 for(int k=1;k<=n;k++) 34 { 35 if(maxbefore<0) maxbefore=before[j][k]-before[i-1][k]; 36 else maxbefore+=before[j][k]-before[i-1][k]; 37 maxmid=max(maxmid,maxbefore); 38 } 39 maxall=max(maxall,maxmid); 40 } 41 } 42 printf("%d\n",maxall); 43 return 0; 44 }
小结：要学会活学活用，这题1A，没错误。