题目描述 Siruseri 政府决定将石油资源丰富的 Navalur 省的土地拍卖给私人承包商以 建立油井。被拍卖的整块土地为一个矩形区域，被划分为 M×N 个小块。 Siruseri 地质调查局有关于 Navalur 土地石油储量的估测数据。这些数据表示 为 M×N 个正整数，即对每一小块土地石油储量的估计值。 为了避免出现垄断，政府规定每一个承包商只能承包一个由 K×K 块相连的 土地构成的正方形区域。 AoE 石油联合公司由三个承包商组成，他们想选择三块互不相交的 K×K 的 区域使得总的收益最大。 例如，假设石油储量的估计值如下：
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 9 9 9 1 1 1 1 1 1 9 9 9 如果 K = 2, AoE 公司可以承包的区域的石油储量总和为 100, 如果 K = 3, AoE 公司可以承包的区域的石油储量总和为 208。 AoE 公司雇佣你来写一个程序，帮助计算出他们可以承包的区域的石油储量 之和的最大值。
输入格式 输入第一行包含三个整数 M, N, K，其中 M 和 N 是矩形区域的行数和列数， K 是每一个承包商承包的正方形的大小（边长的块数）。接下来 M 行，每行有 N 个正整数表示这一行每一小块土地的石油储量的估计值。
输出格式 输出只包含一个正整数，表示 AoE 公司可以承包的区域的石油储量之和的 最大值。
输入输出样例 输入 #1 9 9 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 8 8 8 8 8 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 1 1 8 8 8 1 1 1 1 1 1 9 9 9 1 1 1 1 1 1 9 9 9 输出 #1 208 说明/提示 数据保证 K≤M 且 K≤N 并且至少有三个 K×K 的互不相交的正方形区域。
其 中 30%的输入数据，M, N≤ 12。所有的输入数据, M, N≤ 1500。每一小块土地的 石油储量的估计值是非负整数且≤ 500。
解法：前缀和
#include<cstdio>
#define si 1505
#define re register int
using namespace std
;
int n
,m
,k
,ans
,mp
[si
][si
],a
[si
][si
];
int b
[si
][si
],c
[si
][si
],d
[si
][si
];
inline int read() {
int x
=0,cf
=1;
char ch
=getchar();
while(ch
<'0'||ch
>'9') {
if(ch
=='-') cf
=-1;
ch
=getchar();
}
while(ch
>='0'&&ch
<='9') {
x
=(x
<<3)+(x
<<1)+(ch
^48);
ch
=getchar();
}
return x
*cf
;
}
inline int max(int A
,int B
) { return A
>B
?A
:B
; }
int main() {
n
=read(),m
=read(),k
=read();
for(re i
=1;i
<=n
;i
++) for(re j
=1;j
<=m
;j
++)
mp
[i
][j
]=mp
[i
-1][j
]+mp
[i
][j
-1]-mp
[i
-1][j
-1]+read();
for(re i
=n
;i
>=k
;i
--) for(re j
=m
;j
>=k
;j
--)
mp
[i
][j
]-=mp
[i
-k
][j
]+mp
[i
][j
-k
]-mp
[i
-k
][j
-k
];
for(re i
=k
;i
<=n
;i
++) for(re j
=k
;j
<=m
;j
++)
a
[i
][j
]=max(mp
[i
][j
],max(a
[i
-1][j
],a
[i
][j
-1]));
for(re i
=k
;i
<=n
;i
++) for(re j
=m
;j
>=k
;j
--)
b
[i
][j
]=max(mp
[i
][j
],max(b
[i
-1][j
],b
[i
][j
+1]));
for(re i
=n
;i
>=k
;i
--) for(re j
=k
;j
<=m
;j
++)
c
[i
][j
]=max(mp
[i
][j
],max(c
[i
+1][j
],c
[i
][j
-1]));
for(re i
=n
;i
>=k
;i
--) for(re j
=m
;j
>=k
;j
--)
d
[i
][j
]=max(mp
[i
][j
],max(d
[i
+1][j
],d
[i
][j
+1]));
for(re i
=k
;i
<=n
-k
;i
++) for(re j
=k
;j
<=m
-k
;j
++)
ans
=max(ans
,a
[i
][j
]+b
[i
][j
+k
]+c
[i
+k
][m
]);
for(re i
=k
;i
<=n
-k
;i
++) for(re j
=k
;j
<=m
-k
;j
++)
ans
=max(ans
,a
[i
][m
]+c
[i
+k
][j
]+d
[i
+k
][j
+k
]);
for(re i
=k
;i
<=n
-k
;i
++) for(re j
=k
;j
<=m
-k
;j
++)
ans
=max(ans
,a
[i
][j
]+b
[n
][j
+k
]+c
[i
+k
][j
]);
for(re i
=k
;i
<=n
-k
;i
++) for(re j
=k
;j
<=m
-k
;j
++)
ans
=max(ans
,a
[n
][j
]+b
[i
][j
+k
]+d
[i
+k
][j
+k
]);
for(re i
=k
;i
<=n
-k
;i
++) for(re j
=k
+k
;j
<=m
-k
;j
++)
ans
=max(ans
,a
[n
][j
-k
]+b
[n
][j
+k
]+mp
[i
][j
]);
for(re i
=k
+k
;i
<=n
-k
;i
++) for(re j
=k
;j
<=m
-k
;j
++)
ans
=max(ans
,a
[i
-k
][m
]+c
[i
+k
][m
]+mp
[i
][j
]);
printf("%d",ans
); return 0;
}
