题解矩阵 matrix

矩阵 matrix

Description

给出一个 n × m 的矩阵。请在其中选择至多 3 个互不相交的，大小恰为 k × k 的子矩阵，使得子矩阵的权值和最大。

Input

第一行三个整数 n, m, k ( n, m ≤ 1500) 。

接下来 m 行，每行 n 个整数，描述矩阵。矩阵中的每个元素值都为非负整数，且不超过 500 。

Output

输出一行一个整数，描述答案。

Sample Input

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

Sample Output

解析

这道题似乎并不好写...

因为要使矩阵互不相交...

等等,

如果矩阵互不相交,那么肯定存在两条线,能把三个矩阵分开.

那么,就有六种情况(具体情况自己画一下吧毕竟我画的图丑陋到自己都看不下去),

于是我们可以用\(mp[i][j]\)表示以(\(i\),\(j\))为右下角的矩阵的和,

并用\(a[i][j]\),\(b[i][j]\),\(c[i][j]\),\(d[i][j]\),分别表示点(\(i\),\(j\))左上,右上,左下,右下区域中取一个\(k\)*\(k\)矩阵的最大值,

所以,只需要对于六种情况,分别枚举两条线,并更新答案就行了.

代码可能有点非常丑陋:

#include<bits/stdc++.h>

using namespace std;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}

int n,m,k,ans=0;

int a[1501][1501],c[1501][1501];

int b[1501][1501],d[1501][1501];

int s[1501][1501],mp[1501][1501];

int main(){

	n=read();m=read();k=read();

	for(int i=1;i<=m;i++)

		for(int j=1;j<=n;j++) a[i][j]=read();

	for(int i=1;i<=m;i++)

		for(int j=1;j<=n;j++) s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];

	for(int i=k;i<=m;i++)

		for(int j=k;j<=n;j++) mp[i][j]=s[i][j]-s[i-k][j]-s[i][j-k]+s[i-k][j-k];

	memset(a,0,sizeof(a));

	for(int i=k;i<=m;i++)

		for(int j=k;j<=n;j++) a[i][j]=max(mp[i][j],max(a[i-1][j],a[i][j-1]));

	for(int i=k;i<=m;i++)

		for(int j=k;j<=n;j++) b[i][j]=max(mp[i][j],max(b[i-1][j],b[i][j+1]));

	for(int i=k;i<=m;i++)

		for(int j=k;j<=n;j++) c[i][j]=max(mp[i][j],max(c[i+1][j],c[i][j-1]));

	for(int i=k;i<=m;i++)

		for(int j=k;j<=n;j++) d[i][j]=max(mp[i][j],max(d[i+1][j],d[i][j+1]));

	for(int i=k;i<=m-k;i++)

		for(int j=k;j<=n-k;j++) ans=max(ans,a[i][n]+c[i+k][j]+d[i+k][j+k]);

	for(int i=k;i<=m-k;i++)

		for(int j=k;j<=n-k;j++) ans=max(ans,c[i+k][n]+a[i][j]+b[i][j+k]);

	for(int i=k;i<=m-k;i++)

		for(int j=k;j<=n-k;j++) ans=max(ans,a[m][j]+b[i][j+k]+d[i+k][j+k]);

	for(int i=k;i<=m-k;i++)

		for(int j=k;j<=n-k;j++) ans=max(ans,b[m][j+k]+a[i][j]+c[i+k][j]);

	for(int i=k;i<=m-k;i++)

		for(int j=k+k;j<=n-k;j++) ans=max(ans,a[m][j-k]+mp[i][j]+b[m][j+k]);

	for(int i=k+k;i<=m-k;i++)

		for(int j=k;j<=n-k;j++) ans=max(ans,a[i-k][n]+mp[i][j]+c[i+k][n]);

	printf("%d\n",ans);

	return 0;

}

巴特西

题解矩阵 matrix

矩阵 matrix

Description

Input

Output

Sample Input

Sample Output

解析

最新文章

热门文章

巴特西

题解 矩阵 matrix

矩阵 matrix

Description

Input

Output

Sample Input

Sample Output

解析

最新文章

热门文章

题解矩阵 matrix