题目描述
Siruseri 政府决定将石油资源丰富的 Navalur 省的土地拍卖给私人承包商以 建立油井。被拍卖的整块土地为一个矩形区域，被划分为 M×N 个小块。 Siruseri 地质调查局有关于 Navalur 土地石油储量的估测数据。这些数据表示 为 M×N 个正整数，即对每一小块土地石油储量的估计值。 为了避免出现垄断，政府规定每一个承包商只能承包一个由 K×K 块相连的 土地构成的正方形区域。 AoE 石油联合公司由三个承包商组成，他们想选择三块互不相交的 K×K 的 区域使得总的收益最大。 例如，假设石油储量的估计值如下：
说明
数据保证 K≤M 且 K≤N 并且至少有三个 K×K 的互不相交的正方形区域。
其 中 30%的输入数据，M, N≤ 12。所有的输入数据, M, N≤ 1500。每一小块土地的 石油储量的估计值是非负整数且≤ 500。
题解
弱化版的，可以爆搜即可。
这个是增强版，要dp
可以发现（很难想到），把这个原来的矩形选择3个k*k的正方形区域，
如果我们把大矩形分成3块，总有一种切的方法，可以使得这3个选择的k*k的正方形区域，在每个小的块内都有一块。
一共有6种方法：图片来源
其中，每个正方形在一个小块内随便动。
对于每一个1~6的情况，我们要枚举所有这种形态下的所有情况，计算出最大值，再取max
直接暴力显然不可取。
显然（难以）想到，每个块（除了5,6）都是和边界相交的。
以下所有的i，j表示k*k矩形的右下角，姑且叫代表点
所以，我们设a[i][j],b[i][j],c[i][j],d[i][j],表示，这个代表点在(i,j)左上、右上，左下，右下的所有情况中，k*k正方形最大的总和。
对于a,b,c,d我们都可以以合理的方式递推得到。
然后，再6次nm枚举6种形态的所有情况，取一个mx
注意，(i,j)是代表点的坐标，所以我们循环的边界要注意。必须留出3个正方形的空间。
画图举例想一想就很容易了。
代码：（之后统计的编号对应在图中，都加了注释）
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1505; int s[N][N],a[N][N],b[N][N],c[N][N],d[N][N]; int ans,n,m,k; int main(){ scanf("%d%d%d",&n,&m,&k);int t; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&t),s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+t; 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-1][j],a[i][j-1])); for(int i=k;i<=n;i++) for(int j=m;j>=k;j--) b[i][j]=max(s[i][j],max(b[i][j+1],b[i-1][j])); for(int i=n;i>=k;i--) for(int j=k;j<=m;j++) c[i][j]=max(s[i][j],max(c[i][j-1],c[i+1][j])); for(int i=n;i>=k;i--) for(int j=m;j>=k;j--) d[i][j]=max(s[i][j],max(d[i][j+1],d[i+1][j])); for(int i=k;i<=n-k;i++)//1 for(int j=k;j<=m-k;j++) ans=max(ans,a[i][j]+b[i][j+k]+c[i+k][m]); for(int i=k+k;i<=n;i++)//2 for(int j=k;j<=m-k;j++) ans=max(ans,c[i][j]+d[i][j+k]+a[i-k][m]); for(int i=k+k;i<=n-k;i++)//6 for(int j=k;j<=m;j++) ans=max(ans,s[i][j]+a[i-k][m]+c[i+k][m]); for(int i=k;i<=n-k;i++)//3 for(int j=k;j<=m-k;j++) ans=max(ans,a[i][j]+c[i+k][j]+b[n][j+k]); for(int i=k;i<=n-k;i++)//4 for(int j=k+k;j<=m;j++) ans=max(ans,a[n][j-k]+b[i][j]+d[i+k][j]); for(int i=k;i<=n-k;i++)//5 for(int j=k+k;j<=m-k;j++) ans=max(ans,s[i][j]+a[n][j-k]+b[n][j+k]); printf("%d",ans); return 0; }