题解 P2280 【[HNOI2003]激光炸弹】

· · 题解

Solution

读完题目，我们可以发现：边界上的点是不会被炸掉的。

也就是说，每个边长为 r 的正方形只能覆盖 r^2 个点。

显然， O(n^2m^2) 的枚举算法是要 TLE 的，所以，我们不得不搬出一种神 (la) 奇 (ji) 的算法:

矩阵前缀和：f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+f[i][j]

那么，我们的时间复杂度变成了 O(n^2) ，可以过掉此题。

Code

var n,m,i,x,y,v,mx,my,j,ans:longint;
    f:array[-1..5010,-1..5010] of longint;
begin
  readln(n,m);
  for i:=1 to n do begin
    readln(x,y,v);
    if x>mx then mx:=x;
    if y>my then my:=y;
    f[x+1,y+1]:=v;
  end;
  for i:=1 to 5001 do
    for j:=1 to 5001 do
      f[i,j]:=f[i-1,j]+f[i,j-1]-f[i-1,j-1]+f[i,j];//矩阵前缀和
  for i:=m to 5001 do
    for j:=m to 5001 do if f[i,j]-f[i-m,j]-f[i,j-m]+f[i-m,j-m]>ans then
      ans:=f[i,j]-f[i-m,j]-f[i,j-m]+f[i-m,j-m];//求最值
  writeln(ans);
end.