博客

资源限制


时间限制：2.0s 内存限制：512.0MB

采油区域


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公司可以承包的区域的石油储量之和的最大值。

数据规模和约定


数据保证K≤M且K≤N并且至少有三个K×K的互不相交的正方形区域。其中30%的输入数据，M, N≤ 12。所有的输入数据, M, N≤ 1500。每一小块土地的石油储量的估计值是非负整数且≤ 500。

样例输入

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

样例输出

208

思路

很麻烦的一个题，首先加和的话肯定先算前缀和，常数时间查询一个子矩阵的加和

【

关于矩阵前缀和

】

然后划分出3个不相交的子矩阵，一共有6中划分方式，这里体现了

分治思想




那么如何算每一块的最大值呢？这里要用到动态规划了，而且动态规划要求解四次，分别对应四个问题：

• 矩阵【左上角到(x, y)】的子矩阵中最大加和的
  
k*k

  的矩阵
• 矩阵【右上角到(x, y)】的子矩阵中最大加和的
  
k*k

  的矩阵
• 矩阵【左下角到(x, y)】的子矩阵中最大加和的
  
k*k

  的矩阵
• 矩阵【右下角到(x, y)】的子矩阵中最大加和的
  
k*k

  的矩阵

【

关于这个应用的动态规划求解

】

用四个dp数组，分别为

ul, ur, dl, dr

，表示上述四个动态规划问题的解数组

上述方法求得四个dp矩阵，那么可以开始暴力穷举每一种分法的边界，这里体现了

枚举思想

对于1-4种分法，穷举点，比如

分法3

，点将矩阵分为三个区域：左上，左下，右边

对于5-6种分法，穷举中间的两个横杠，横杠的间距为k，那么问题变为：上面，中间，下面

上下的最值好求，中间的最值需要枚举另一坐标轴，滑动一个k*k的矩阵，这矩阵夹在两横杠中间滑动，寻找最大值

代码

#include <bits/stdc++.h>

using namespace std;

int a[1509][1509], ul[1509][1509], ur[1509][1509], dl[1509][1509], dr[1509][1509];
int m, n, k;

int kksum(int x1, int y1, int x2, int y2)
{
	return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}

int main()
{	
	cin>>m>>n>>k;
	memset(a, 0, sizeof(a));
	memset(ul, 0, sizeof(ul));
	memset(ur, 0, sizeof(ur));
	memset(dl, 0, sizeof(dl));
	memset(dr, 0, sizeof(dr));
	
	// 计算行前缀和 
	for(int i=1; i<=m; i++)
		for(int j=1; j<=n; j++) 
			cin>>a[i][j], a[i][j]+=a[i][j-1]; 
	// 计算列前缀和 
	for(int i=1; i<=m; i++)
		for(int j=1; j<=n; j++)
			a[i][j] += a[i-1][j];
	// ul
	for(int i=k; i<=m; i++)
		for(int j=k; j<=n; j++)
			ul[i][j] = max(kksum(i-k+1, j-k+1, i, j), max(ul[i-1][j], ul[i][j-1]));
	// ur	
	for(int i=k; i<=m; i++)
		for(int j=n-k+1; j>=1; j--)
			ur[i][j] = max(kksum(i-k+1, j, i, j+k-1), max(ur[i-1][j], ur[i][j+1]));
	// dl		
	for(int i=m-k+1; i>=1; i--)
		for(int j=k; j<=n; j++)
			dl[i][j] = max(kksum(i, j-k+1, i+k-1, j), max(dl[i+1][j], dl[i][j-1]));
	// dr	
	for(int i=m-k+1; i>=1; i--)
		for(int j=n-k+1; j>=1; j--) 
			dr[i][j] = max(kksum(i, j, i+k-1, j+k-1), max(dr[i+1][j], dr[i][j+1]));
	
	int ans = 0;
	// 枚举点，对应分法1-4 
	for(int i=1; i+1<=m; i++)
	{
		for(int j=1; j+1<=n; j++)
		{
			ans = max(ans, ul[i][n]+dl[i+1][j]+dr[i+1][j+1]);
			ans = max(ans, dr[i+1][1]+ul[i][j]+ur[i][j+1]);
			ans = max(ans, ur[m][j+1]+ul[i][j]+dl[i+1][j]);
			ans = max(ans, dl[1][j]+ur[i][j+1]+dr[i+1][j+1]);
		}
	}
	// 枚举中间的横杠，对应分法5-6 
	for(int i=k; i+k+1<=m; i++)
	{
		int up = ul[i][n];
		int dw = dl[i+k+1][n];
		int mid = 0;
		for(int j=k; j<=n; j++)
			mid = max(mid, kksum(i+1, j-k+1, i+k, j));
		ans = max(ans, up+dw+mid);
	}		
	for(int j=k; j+k+1<=n; j++)
	{
		int le = max(ul[k][j], dl[k+1][j]);
		int ri = max(ur[k][j+k+1], dr[k+1][j+k+1]);
		int mid = 0;
		for(int i=k; i<=m; i++)
			mid = max(mid, kksum(i-k+1, j+1, i, j+k));
		ans = max(ans, le+ri+mid);
	}
	
	cout<<ans<<endl;
	
	return 0;
}