糖果盒

发布于 2019-04-04  25 次阅读


题目描述

一个被分为 n*m 个格子的糖果盒,第 i 行第 j 列位置的格子里面有 a [ i ][ j ] 颗糖。本来 tenshi 打算送这盒糖果给某 PPMM 的,但是就在要送出糖果盒的前一天晚上,一只极其可恶的老鼠夜袭糖果盒,有部分格子被洗劫并且穿了洞。tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒,新的糖果盒不能有洞,并且 tenshi 希望保留在新糖果盒内的糖的总数尽量多。
请帮tenshi设计一个程序 计算一下新糖果盒最多能够保留多少糖果

输入

从文件CANDY.IN读入数据。第一行有两个整数 n、m。第 i + 1 行的第 j 个数表示 a [ i ][ j ],如果这个数为 0 ,则表示这个位置的格子被洗劫过。其中:
1 ≤ n,m ≤ 300
0 ≤ a [ i ][ j ]≤ 255

输出

输出最大糖果数

思路

用最大子矩阵的优化方法,在输入时间空缺付为-maxlongint就可以了

var
  a:array[-10..5000,-10..5000] of longint;
  f,p:array[-10..1000] of int64;
  i,j,k,n,m,s,x,y,max:longint;
begin
  readln(n,m);
  max:=-maxlongint;
  for i:=1 to n do
    begin
      for j:=1 to m do
        begin
          read(a[i,j]);
          if a[i,j]=0 then a[i,j]:=-maxlongint+1000;
        end;
      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
]]>