题目大意
给定一个矩阵，求出其三个$K\times K$互不相交的最大子正方形的权值和。
初步想法
三个互不相交$K\times K$子正方形？
两个子矩阵的时候我们可以使用预处理+枚举分割线的算法$O(n^2)$解决。
但是三个子正方形呢？
我们肯定还是要枚举分割线（共有6种情况）：
前4种情况：
对于这四种情况的处理需要从四个方向递推子正方形，比较麻烦，但代码相似。
后两种情况：
对于这两种情况的处理就没有办法使用上面的方法了。
这时我们可以将两个边界之间的距离卡到刚好为$K$，这样经过预处理可以$O(1)$询问。
具体算法
首先预处理出：
$fLU[i,j]$：以$(1,1)$为左上角$(i,j)$为右下角的矩阵中的最大子正方形。
$fLD[i,j]$：以$(n,1)$为左下角$(i,j)$为右上角的矩阵中的最大子正方形。
$fRU[i,j]$：以$(1,m)$为右上角$(i,j)$为左下角的矩阵中的最大子正方形。
$fRD[i,j]$：以$(n,m)$为右下角$(i,j)$为左上角的矩阵中的最大子正方形。
①
对于上面的情况1：
枚举分割线$x$，枚举分割线$y$，使用$fLU[x,y]+fRU[x,y+1]+fLD[x+1,m]$更新答案。
其余的三种类似且方法不唯一，不再赘述，用下图一目了然的解释。
②对于后两种情况：
通过将两条分割线中间夹k的距离强行去掉部分重复枚举情况。
对于第五种情况：
设$f[i]$表示$x1=i$,$x2=i+K-1$中的最大子正方形权值和。
然后使用$fLU[x,m]+f[x+1]+fRD[x+K+1,1]$更新答案。
第六种情况类似，见图。
代码
其实代码还是挺简单的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,m,K,ans=-0x7fffffff/2,map[1505][1505],s[1505][1505],sum[1505][1505],fLU[1505][1505],fRU[1505][1505],fLD[1505][1505],fRD[1505][1505],f1[1505],f2[1505];
int Sum(int x1,int y1,int x2,int y2) {
return sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
}
int main() {
n=Get_Int();
m=Get_Int();
K=Get_Int();
//1.初始化前缀和
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
map[i][j]=Get_Int();
s[i][j]=s[i][j-1]+map[i][j];
sum[i][j]=sum[i-1][j]+s[i][j];
}
//2.求出四个方向最大子矩阵
for(int i=K; i<=n; i++)
for(int j=K; j<=m; j++)
fLU[i][j]=max(max(fLU[i-1][j],fLU[i][j-1]),Sum(i-K+1,j-K+1,i,j));
for(int i=K; i<=n; i++)
for(int j=m-K+1; j>=1; j--)
fRU[i][j]=max(max(fRU[i-1][j],fRU[i][j+1]),Sum(i-K+1,j,i,j+K-1));
for(int i=n-K+1; i>=1; i--)
for(int j=K; j<=m; j++)
fLD[i][j]=max(max(fLD[i+1][j],fLD[i][j-1]),Sum(i,j-K+1,i+K-1,j));
for(int i=n-K+1; i>=1; i--)
for(int j=m-K+1; j>=1; j--)
fRD[i][j]=max(max(fRD[i+1][j],fRD[i][j+1]),Sum(i,j,i+K-1,j+K-1));
//3.计算可能情况中一横一竖的四种情况
for(int x=K; x<=n-K; x++) //情况1
for(int y=K; y<=m-K; y++)
ans=max(ans,fLU[x][y]+fRU[x][y+1]+fLD[x+1][m]);
for(int x=K; x<=n-K; x++) //情况2
for(int y=K; y<=m-K; y++)
ans=max(ans,fLU[x][m]+fLD[x+1][y]+fRD[x+1][y+1]);
for(int y=K; y<=m-K; y++) //情况3
for(int x=K; x<=n-K; x++)
ans=max(ans,fLU[x][y]+fLD[x+1][y]+fRU[n][y+1]);
for(int y=K; y<=m-K; y++) //情况4
for(int x=K; x<=n-K; x++)
ans=max(ans,fLU[n][y]+fRU[x][y+1]+fRD[x+1][y+1]);
//4.计算可能情况中横横竖竖的两种情况
for(int x=K+1; x<=n-2*K; x++) //情况5预处理
for(int y=1; y<=m-K+1; y++)
f1[x]=max(f1[x],Sum(x,y,x+K-1,y+K-1));
for(int x=K; x<=n-2*K; x++)ans=max(ans,fLU[x][m]+f1[x+1]+fRD[x+K+1][1]); //枚举第一条横线（第二条：x+K）计算答案
for(int y=K+1; y<=m-2*K; y++)
for(int x=1; x<=n-K+1; x++)
f2[y]=max(f2[y],Sum(x,y,x+K-1,y+K-1));
for(int y=K; y<=m-2*K; y++)ans=max(ans,fLU[n][y]+f2[y+1]+fRD[1][y+K+1]);
printf("%d\n",ans);
return 0;
}
