忍·甜甜圈

题目简述

$n×m$ 的网格图，每个格子有权值，选三个不重叠的 $k×k$ 的正方形区域，求最大权值和。

$n,m≤1500$

思路

数据范围看起来很暴力，实际也很暴力。

首先可以看出如果三个正方形一起枚举的话肯定是行不通的。但是我们可以考虑根据正方形的位置把网格图用两条线段分成不重叠的三部分 —— 每部分里面求一个最大的正方形区域。三个正方形可以横着一排或者竖着一列，又或者是形成一个三角形 —— 这种情况有四个方向。于是只要先对网格图二维前缀和预处理，就可以分类讨论暴力统计了。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
const int MaxN = 1503;
int n, m, k, sum[MaxN][MaxN], sq[MaxN][MaxN], ans;
int rb[MaxN][MaxN], lb[MaxN][MaxN], rt[MaxN][MaxN], lt[MaxN][MaxN];

inline int Read(){
	int num = 0, op = 1;
	char ch = getchar();
	while(!isdigit(ch)){
		if(ch == '-') op = -1;
		ch = getchar();
	}
	while(isdigit(ch)){
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return num * op;
}

signed main(){
	n = Read(), m = Read(), k = Read();
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			int val = Read();
			sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + val;
		}
	}
	
	for(int i=k; i<=n; i++)
		for(int j=k; j<=m; j++)
			sq[i][j] = sum[i][j] - sum[i-k][j] - sum[i][j-k] + sum[i-k][j-k];
			
	for(int i=k; i<=n; i++)
		for(int j=k; j<=m; j++)
			rb[i][j] = max(sq[i][j], max(rb[i-1][j], rb[i][j-1]));
			
	for(int i=k; i<=n; i++)
		for(int j=m-k+1; j; j--)
			lb[i][j] = max(sq[i][j+k-1], max(lb[i-1][j], lb[i][j+1]));
			
	for(int i=n-k+1; i; i--)
		for(int j=k; j<=m; j++)
			rt[i][j] = max(sq[i+k-1][j], max(rt[i+1][j], rt[i][j-1]));
	
	for(int i=n-k+1; i; i--)
		for(int j=m-k+1; j; j--)
			lt[i][j] = max(sq[i+k-1][j+k-1], max(lt[i+1][j], lt[i][j+1]));
			
	for(int i=k; i<=n; i++)
		for(int j=k+k; j<=m-k; j++)
			ans = max(ans, sq[i][j] + rb[n][j-k] + lb[n][j+1]);
			
	for(int i=k+k; i<=n-k; i++)
		for(int j=k; j<=m; j++)
			ans = max(ans, sq[i][j] + rb[i-k][m] + rt[i+1][m]);
	
	for(int i=k; i<=n-k; i++)
		for(int j=k; j<=m-k; j++)
			ans = max(ans, rb[i][j] + rt[i+1][j] + lt[1][j+1]);
	
	for(int i=k; i<=n-k; i++)
		for(int j=k; j<=m-k; j++)
			ans = max(ans, rb[n][j] + lb[i][j+1] + lt[i+1][j+1]);
	
	for(int i=k; i<=n-k; i++)
		for(int j=k; j<=m-k; j++)
			ans = max(ans, rb[i][j] + lb[i][j+1] + lt[i+1][1]);
	
	for(int i=k; i<=n-k; i++)
		for(int j=k; j<=m-k; j++)
			ans = max(ans, rb[i][m] + rt[i+1][j] + lt[i+1][j+1]);
			
	printf("%lld", ans);
	return 0;
}