旅行__矩阵取数问题(最大子矩阵)(n三次方(略小一些)做法)

发布于 2019-04-03  11 次阅读


题目描述

ACM队员们到Z镇游玩,Z镇是一个很特别的城镇,它有m+1条东西方向和n+1条南北方向的道路,划分成M*N个区域。Z镇的名胜位于这些区域内,从上往下第i行,从左往右数第j列的区域记为D(i,j)。ACM队员们预先对这M*N个区域打分V(i,j)(分数可正可负)。分数越高表示他们越想到那个地方,越低表示他们越不想去。为了方便集合,队员们只能在某一个范围内活动。我们可以用(m1,n1)与(m2,n2)(m1<=m2,n1<=n2)表示这样一个范围:它是这些区域的集合: ,ACM队员希望他们活动区域的分值总和最大。
当然,有的队员可能一个也不去(例如,所有区域的分值都是负数。当然,如果某范围内的分值和为0的话,他们也不会去玩)。也有可能他们游览整个Z镇。你的任务是编写一个程序,求出他们的活动范围(m1,n1),(m2,n2)。

输入

输入有m+1行,第一行有两个整数m,n(m,n定义如上)。其中( ),接下来的m行,每行n个整数,第i行第j个数表示分数V(i,j)。(-128<=v(i,j)<=127)每两个整数之间有一个空格。

输出

输入只一行,分两种情况:
1. 队员在范围内(m1,n2)(m2,n2)内活动,输出该范围内的分值。
2. 队员们任何地方都不去,只需输出NO。
注意:不要输出多余的空行,行首行尾不要有多余的空格。

思路

枚举行m1,m2,在行m1,m2之间的元素中,把同一列的元素加起来(即把二维压缩成一维),然后用最大子序列的方法求解,就是做n多边最大子序列,就可以枚举到每一种情况。

var
  a:array[-10..1000,-10..1000] of longint;
  f,p:array[-10..1000] of longint;
  i,j,k,n,m,s,x,y,max:longint;
begin
  readln(n,m);
  max:=-1000;
  for i:=1 to n do
    begin
      for j:=1 to m do
        read(a[i,j]);
      readln;
    end;

  for i:=1 to n do
    begin
      fillchar(f,sizeof(f),0);
      for j:=1 to m do p[j]:=a[i,j];
      for j:=1 to m do
        begin
          if p[j]+f[j-1]>=0 then begin f[j]:=p[j]+f[j-1]; if max=0 then begin f[k]:=p[k]+f[k-1]; if max
]]>