[DP ~ 최대 서브 매트릭스] 석재 절단

석재 절단 
질문 설명:
누 군 가 는 N * M 개의 작은 칸 의 사각형 석재 (옥석 일 수 있 음) 를 얻 었 다. 전문가 의 분석 을 통 해 이 사각형 석재 의 모든 작은 칸 은 하나의 가치 (절대 치가 10 보다 크 지 않 은 정수 로 묘사) 가 있다. 지금 은 이 석 재 를 두 개의 사각형 석재 로 자 르 고 주 의 를 기울 인 다. 절단 은 이 사각형 의 변 과 평행 할 수 밖 에 없다. 즉, 사각형 의 작은 칸 을 잘 라 낼 수 없다 는 것 이다.각 사각형 석재 의 가 치 를 이 사각형 의 모든 작은 격자 가치 의 합 이 라 고 가정 합 니 다.
    어떻게 절단 해 야 이 두 사각형 의 가 치 를 곱 할 수 있 는 지 물 었 다.아래 그림 과 같이 비교적 좋 은 절단 방식 이다.
입력 형식:
파일 BRICK. IN 의 첫 번 째 행동 2 개의 정수 N 과 M 을 입력 하면 석재 가 N * M 칸 으로 나 뉘 어 져 있 음 을 나타 낸다.다음 N 줄 은 줄 마다 M 개의 정수 가 있 는데 이 칸 의 가 치 를 대표 합 니 다.
 
출력 형식:
출력 파일 BRICK. OUT 는 한 줄 만 있 고 하나의 정 수 를 포함 하 며 두 사각형 의 가치 의 최대 곱 하기 입 니 다.
 
입력 샘플
출력 샘플
3 4 -1 -1 -1 -1 0 0 0 0 -1 -1 -1 -1
16
 
데이터 범위
30% 의 데이터 에 대해 N, M ≤ 5 만족.
100% 의 데이터 에 대하 여 N, M ≤ 100 만족.각 작은 칸 의 데 미 지 의 절대 치 는 10 을 초과 하지 않 습 니 다.
모든 데이터 와 중간 변 수 는 longint 범 위 를 초과 하지 않 습 니 다.
==================================
============================================
제 가 시작 한 알고리즘 O (n ^ 4) [90 점]
제 가 먼저 접선 을 매 거 했 는데... 만점 알고리즘 보다 1 차원 이 더 많아 요.
------------------------------------
[나의 알고리즘.]

var
  n,m:longint;
  map:array[1..100,1..100]of longint;
  sum:array[1..100,0..100]of longint;
  f1,f2:array[0..100]of longint;
procedure init;
begin
  assign(input,'brick.in');
  assign(output,'brick.out');
  reset(input); rewrite(output);
end;

procedure terminate;
begin
  close(input); close(output);
  halt;
end;

procedure main;
var
  i,j:longint;
  max,min:longint;
  s_min1,s_max1,s_min2,s_max2:longint;
  ans:longint;
  n1,n2:longint;
  now:longint;
begin
  readln(n,m);
  fillchar(sum,sizeof(sum),0);
  for i:=1 to n do
    for j:=1 to m do
      begin
        read(map[i,j]);
        sum[i,j]:=sum[i-1,j]+map[i,j];
      end;
  
  ans:=-maxlongint;
  
  for i:=1 to n-1 do
    begin
      s_min1:=maxlongint;
      s_min2:=maxlongint;
      s_max1:=-maxlongint;
      s_max2:=-maxlongint;
      for n1:=1 to i do
        for n2:=n1 to i do
          begin
            //fillchar(f1,sizeof(f1),0);  //max
            //fillchar(f2,sizeof(f2),0);  //min
            f1[0]:=0;
            f2[0]:=0;
            for j:=1 to m do
              begin
                now:=sum[n2,j]-sum[n1-1,j];
                if nowf1[j-1]+now then f1[j]:=now
                                   else f1[j]:=f1[j-1]+now;
                if f1[j]>s_max1 then s_max1:=f1[j];
                if f2[j]f1[j-1]+now then f1[j]:=now
                                   else f1[j]:=f1[j-1]+now;
                if f1[j]>s_max2 then s_max2:=f1[j];
                if f2[j]ans then ans:=s_min1*s_min2;
      if s_max1*s_max2>ans then ans:=s_max1*s_max2;
    end;

  for i:=1 to m-1 do
    begin
      s_min1:=maxlongint;
      s_min2:=maxlongint;
      s_max1:=-maxlongint;
      s_max2:=-maxlongint;
      for n1:=1 to n do
        for n2:=n1 to n do
          begin
            //fillchar(f1,sizeof(f1),0);  //max
            //fillchar(f2,sizeof(f2),0);  //min
            f1[0]:=0;
            f2[0]:=0;
            for j:=1 to i do
              begin
                now:=sum[n2,j]-sum[n1-1,j];
                if nowf1[j-1]+now then f1[j]:=now
                                   else f1[j]:=f1[j-1]+now;
                if f1[j]>s_max1 then s_max1:=f1[j];
                if f2[j]f1[j-1]+now then f1[j]:=now
                                   else f1[j]:=f1[j-1]+now;
                if f1[j]>s_max2 then s_max2:=f1[j];
                if f2[j]ans then ans:=s_min1*s_min2;
      if s_max1*s_max2>ans then ans:=s_max1*s_max2;
    end;
  writeln(ans);
end;
begin
  init;
  main;
  terminate;
end.

-------------------------------------
만점 알고리즘 은 대략 O (n ^ 3) 와 같다.
접선 을 매 거 할 필요 가 없다.
-----------------------------------------------
[만점 알고리즘]

var
  n,m:longint;
  map:array[1..100,1..100]of longint;
  sum:array[0..100,0..100]of longint;
  j1,j2:array[1..100,1..100]of longint;
  f1,f2:array[0..100]of longint;
procedure init;
begin
  assign(input,'brick.in');
  assign(output,'brick.out');
  reset(input); rewrite(output);
end;

procedure terminate;
begin
  close(input); close(output);
  halt;
end;

procedure main;
var
  i,j:longint;
  max,min:longint;
  s_min1,s_max1:longint;
  ans:longint;
  n1,n2,m1,m2:longint;
  now:longint;
begin
  readln(n,m);
  fillchar(sum,sizeof(sum),0);
  
  for i:=1 to n do
    for j:=1 to m do
      begin
        read(map[i,j]);
        sum[i,j]:=sum[i-1,j]+map[i,j];
      end;

  ans:=-maxlongint;
//--------------------------------------------------------------->   ...

  fillchar(j1,sizeof(j1),0);
  fillchar(j2,sizeof(j2),0);
  for n1:=1 to n do
    for n2:=n1 to n do
      begin
        f1[0]:=0;
        f2[0]:=0;
        s_min1:=maxlongint;
        s_max1:=-maxlongint;
        for j:=1 to m do
          begin
            now:=sum[n2,j]-sum[n1-1,j];
            if nowf1[j-1]+now then f1[j]:=now
                               else f1[j]:=f1[j-1]+now;
            if f1[j]>s_max1 then s_max1:=f1[j];
            if f2[j]ans then ans:=j1[n1,n2]*j1[m1,m2];
            if j2[n1,n2]*j2[m1,m2]>ans then ans:=j2[n1,n2]*j2[m1,m2];
          end;
//----------------------------------------------------------> n       ..
  fillchar(sum,sizeof(sum),0);
  for i:=1 to n do
    for j:=1 to m do
      begin
        sum[i,j]:=sum[i,j-1]+map[i,j];
      end;

  s_min1:=maxlongint;
  s_max1:=-maxlongint;
  for m1:=1 to m do
    for m2:=m1 to m do
      begin
        f1[0]:=0;
        f2[0]:=0;
        s_min1:=maxlongint;
        s_max1:=-maxlongint;
        for j:=1 to n do
          begin
            now:=sum[j,m2]-sum[j,m1-1];
            if nowf1[j-1]+now then f1[j]:=now
                               else f1[j]:=f1[j-1]+now;
            if f1[j]>s_max1 then s_max1:=f1[j];
            if f2[j]ans then ans:=j1[n1,n2]*j1[m1,m2];
          if j2[n1,n2]*j2[m1,m2]>ans then ans:=j2[n1,n2]*j2[m1,m2];
        end;
//---------------------------------------------------------> m      ..
  writeln(ans);
end;
begin
  init;
  main;
  terminate;
end.