SSL 2315_打砖块_dp

发布于 2019-05-17  8 次阅读


题目描述

 KXT是一个很无聊的小朋友,一天到晚都在打坐……
  一天,被他发现了一个比打坐更无聊的事情——打砖块。很多块砖分布在一个m*m的矩阵中,他可以消掉以他为左上角顶点的一个n*n的矩阵里的所有砖块。
  喜欢偷懒的他请来了你帮他计算可以消掉最多的砖块数(只能消一次)。


思路

dp f[i,j]=f[i−1,j]+f[i,j−1]−f[i−1,j−1]
然后在记录时把加过的减掉,在把多减的加上


var
  f,a:array[-1000..1001,-1000..1001] of int64;
  x,y,r,c,i,j,k,n,m,s:longint;
  max:int64;
begin
  readln(r,m,n);
  for i:=1 to n do
    begin
      readln(x,y);
      f[x,y]:=1;
    end;
  c:=r;
  for i:=1 to m do
    for j:=1 to m do
      begin
        f[i,j]:=f[i,j]+f[i-1,j]+f[i,j-1]-f[i-1,j-1];
        if f[i,j]+f[i-r,j-c]-f[i-r,j]-f[i,j-c]>max then max:=f[i,j]+f[i-r,j-c]-f[i-r,j]-f[i,j-c];
      end;
  writeln(max);
end.
]]>