...
题目：题意：分析：代码：
题目：
题目传送门
题意：
有一张
n
∗
n
n*n
n∗n的图，我们需要选出
3
3
3个
k
∗
k
k*k
k∗k的正方形，使得它们的和最大
分析：
我们对于每个点分成四个区域
：
：
： 各自代表在该区域里最大的
k
∗
k
k*k
k∗k矩阵的值是多少 对于完整的
n
∗
n
n*n
n∗n的图来说，答案所求的三个矩阵无非是有
6
6
6中分布情况
：
：
：
在这前四种情况下，我们枚举中间的横线与竖线，用
a
,
b
,
c
,
d
a,b,c,d
a,b,c,d结合交点算出来三个区域的最大值的和
剩下这两种情况相对特殊，我们会发现，两边的区域很好表示，但对于中间的却没有操作空间，那我们就只能回到最原始的方法 设
s
i
,
j
s_{i,j}
si,j表示以
i
,
j
i,j
i,j为右下角的
k
∗
k
k*k
k∗k的正方形的数值和，这个
s
s
s相当于一个二维前缀和，并且有了
s
s
s，对于
a
,
b
,
c
,
d
a,b,c,d
a,b,c,d都会更好推出 现在中间的区域我们就通过暴力枚举出每一个
k
∗
k
k*k
k∗k的正方形来计算答案，更形象的，就是两边先不变，把中间都枚举完毕后，两边再换范围，再枚举中间…
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#define LL long long
using namespace std
;
inline LL
read()
{
LL s
=0,f
=1; char c
=getchar();
while(c
<'0'||c
>'9') {if(c
=='-') f
=-1;c
=getchar();}
while(c
>='0'&&c
<='9') {s
=s
*10+c
-'0';c
=getchar();}
return s
*f
;
}
int p
,s
[1505][1505];
int a
[1505][1505],b
[1505][1505],c
[1505][1505],d
[1505][1505];
int main()
{
int n
=read(),m
=read(),k
=read();
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=m
;j
++)
{
int p
=read();
s
[i
][j
]=s
[i
-1][j
]+s
[i
][j
-1]-s
[i
-1][j
-1]+p
;
}
for(int i
=n
;i
>=k
;i
--) for(int j
=m
;j
>=k
;j
--) s
[i
][j
]-=s
[i
-k
][j
]+s
[i
][j
-k
]-s
[i
-k
][j
-k
];
for(int i
=k
;i
<=n
;i
++) for(int j
=k
;j
<=m
;j
++) a
[i
][j
]=max(s
[i
][j
],max(a
[i
][j
-1],a
[i
-1][j
]));
for(int i
=k
;i
<=n
;i
++) for(int j
=m
-k
+1;j
;j
--) b
[i
][j
]=max(s
[i
][j
+k
-1],max(b
[i
][j
+1],b
[i
-1][j
]));
for(int i
=n
-k
+1;i
;i
--) for(int j
=k
;j
<=m
;j
++) c
[i
][j
]=max(s
[i
+k
-1][j
],max(c
[i
+1][j
],c
[i
][j
-1]));
for(int i
=n
-k
+1;i
;i
--) for(int j
=m
-k
+1;j
;j
--) d
[i
][j
]=max(s
[i
+k
-1][j
+k
-1],max(d
[i
+1][j
],d
[i
][j
+1]));
int ans
=0;
for(int i
=k
;i
<=n
-k
;i
++) for(int j
=k
;j
<=m
-k
;j
++)
{
ans
=max(ans
,a
[i
][j
]+b
[i
][j
+1]+c
[i
+1][m
]);
ans
=max(ans
,a
[i
][j
]+c
[i
+1][j
]+d
[1][j
+1]);
ans
=max(ans
,a
[i
][m
]+c
[i
+1][j
]+d
[i
+1][j
+1]);
ans
=max(ans
,a
[n
][j
]+b
[i
][j
+1]+d
[i
+1][j
+1]);
}
for(int i
=k
;i
<=n
-2*k
;i
++) for(int j
=k
;j
<=m
;j
++) ans
=max(ans
,a
[i
][m
]+s
[i
+k
][j
]+d
[i
+k
+1][1]);
for(int i
=k
;i
<=n
;i
++) for(int j
=k
;j
<=m
-2*k
;j
++) ans
=max(ans
,a
[n
][j
]+s
[i
][j
+k
]+d
[1][j
+k
+1]);
cout
<<ans
;
return 0;
}
