题目大意就是求一个矩阵中的最大子矩阵和。
求最大子矩阵和可以看作求最大子段和的二维平面版本，因此基本思路就是降维，将一行或一列进行压缩，然后再转化成求一维线段上的最大子段和。具体实现时可以用b[i,j]表示第j列从第1行到第i行的数字和，限定列压缩的起始行和结束行，用c[j]表示当前限制下到第j列为止的最大子矩阵和。记录下c[j]出现过的最大值即为最大子矩阵和。
7731901 IwfWcf 1050 Accepted 780K 47MS G++ 724B 2010-10-11 21:52:23
帖子
0 评论:
发表评论