题目:在幻想乡,射命丸文是以偷拍闻名的鸦天狗。当然,文文的照相机可不止能够照相,还能够消除取景框里面所有的弹幕。假设现在文文面前有一块N行M列的弹幕群,每一个单位面积内有分值有num[i][j]的弹幕。相机的取景框可以将一块R行C列的弹幕消除,并且得到这一块区域内所有弹幕的分值(累加)。现在文文想要取得尽可能多的分值,请你计算出她最多能够得到的分值。
分析:
用F来初始化,表示以(1,1)为顶点,(i,J)为右下角点构成的矩形之中的数的和,再枚举每一个点,用ans:=max(ans,f[i,j]-f[i-r,j]-f[i,j-c]+f[i-r,j-c]);来求R*C矩阵的值,最后输出ans。
附上程序:
const maxn=1000; var n,m,r,c,ans:longint; f:array [-maxn..maxn,-maxn..maxn] of longint; procedure init; var i,j,num:longint; begin readln(n,m,r,c); for i:=1 to n do for j:=1 to m do begin read(num); f[i,j]:=f[i-1,j]+f[i,j-1]-f[i-1,j-1]+num; end; end; function max(a,b:longint):longint; begin if a>b then exit(a); exit(b); end; procedure main; var i,j:longint; begin for i:=1 to n do for j:=1 to m do ans:=max(ans,f[i,j]-f[i-r,j]-f[i,j-c]+f[i-r,j-c]); write(ans); end; begin init; main; end.