题目分类：分类讨论，前缀和

题意：

给出一个矩阵，要求从中取出三个不相交的边长为k的正方形使得和最大。

题解：

通过将每个点转化为以他为左上角的正方形可以将问题转化为求出距离大于k的三个值使得和最大，考虑这三个值处在的位置关系，可以分六种情况讨论。讨论过程中需要注意对于两横或两竖的情况可以直接枚举中间的。

使用前缀和和前缀最大就可以了。

程序：

#include<cstdio>
#include<algorithm>
using namespace std;
int a[1600][1600],b[1600][1600];
int n,m;
int leftup[1600][1600],rightup[1600][1600];
int leftdown[1600][1600],rightdown[1600][1600];
int ans,k;
int main()
{
	scanf("%d %d %d",&n,&m,&k);
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
			a[i][j]=a[i-1][j]+a[i][j];
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			a[i][j]=a[i][j-1]+a[i][j];
			if(i-k>=0&&j-k>=0)
			{
				b[i][j]=a[i][j]+a[i-k][j-k]-a[i-k][j]-a[i][j-k];
			}
		}
	}
	for (int i=k;i<=n;i++)
	{
		for (int j=k;j<=m;j++)
		{
			leftup[i][j]=max(b[i][j],max(leftup[i][j-1],leftup[i-1][j]));
		}
	}
	for (int i=k;i<=n;i++)
	{
		for (int j=m;j>=k;j--)
		{
			rightup[i][j]=max(b[i][j],max(rightup[i][j+1],rightup[i-1][j]));
		}
	}
	for (int i=n;i>=k;i--)
	{
		for (int j=k;j<=m;j++)
		{
			leftdown[i][j]=max(b[i][j],max(leftdown[i][j-1],leftdown[i+1][j]));
		}
	}
	for (int i=n;i>=k;i--)
	{
		for (int j=m;j>=k;j--)
		{
			rightdown[i][j]=max(b[i][j],max(rightdown[i][j+1],rightdown[i+1][j]));
		}
	}
	for (int i=k;i<=n;i++)
	{
		for (int j=k+k;j<=m-k;j++)
		{
			ans=max(ans,b[i][j]+leftup[n][j-k]+rightup[n][j+k]);
		}
	}
	for (int i=k+k;i<=n-k;i++)
	{
		for (int j=k;j<=m;j++)
		{
			ans=max(ans,b[i][j]+leftup[i-k][m]+leftdown[i+k][m]);
		}
	}
	for (int i=k;i<=n-k;i++)
	{
		for (int j=k;j<=n-k;j++)
		{
			ans=max(ans,leftup[i][j]+rightup[i][j+k]+leftdown[i+k][m]);
			ans=max(ans,leftup[i][j]+leftdown[i+k][j]+rightup[n][j+k]);
			ans=max(ans,leftup[i][m]+leftdown[i+k][j]+rightdown[i+k][j+k]);
			ans=max(ans,leftup[n][j]+rightup[i][j+k]+rightdown[i+k][j+k]);
		}
	}printf("%d\n",ans);
	return 0;
}