自动搬运

查看原文

来自洛谷，原作者为

	wsyhb **

搬运于2025-08-24 22:27:11，当前版本为作者最后更新于2021-01-24 16:31:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述

定义矩阵环为将矩阵中的一个非空子矩阵去掉后得到的图形，给定一个 $n \times m$ 的矩阵 $a$，问所有上下厚度均为 $1$ 的矩阵环的元素之和的最大值。

数据范围：$n \le 10$，$m \le 10^5$，$|a_{i,j}| \le 100$

分析 + 题解

考虑将矩阵环拆成左、中、右三个部分：

--+++++++++-    --+++ ++++ ++-
--+++----++-    --+++ ---- ++-
--+++----++- -> --+++ ---- ++-
--+++----++-    --+++ ---- ++-
--+++++++++-    --+++ ++++ ++-

由此可见，矩阵环左、右两部分为若干个完整的列，中间部分为若干个只有上下两行的列，且左、中、右三部分都必须非空。考虑分三个阶段进行 DP。

记 $s_i$ 为第 $i$ 列元素之和，$t_i$ 为第 $i$ 列首尾元素之和，设 $dp1_i$ 表示以第 $i$ 列为止的左边部分的元素之和最大值，$dp2_i$ 表示以第 $i$ 列为止的左、中部分的元素之和最大值，$dp3_i$ 表示以第 $i$ 列为止的左、中、右部分的元素之和最大值，则有下列转移方程：

说明：每一阶段可以由这一部分或上一部分加上这一列转移而来。由于每一部分必须非空，$dp1_0=dp2_0=dp3_0=-inf$。

别忘了若 $n \le 2$ 或 $m \le 2$，不存在矩阵环，即无解。

代码

代码非常地好写~

#include<bits/stdc++.h>
using namespace std;
const int max_n=10+5;
const int max_m=1e5+5;
int s[max_m],t[max_m];
int dp1[max_m],dp2[max_m],dp3[max_m];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	if(n<=2||m<=2)//判无解 
	{
		puts("-1");
		return 0;
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j)
		{
			int a;
			scanf("%d",&a);
			s[j]+=a;
			if(i==1||i==n)
				t[j]+=a;
		}//直接读入并更新 s 和 t，无需存储 
	dp1[0]=dp2[0]=dp3[0]=-1e9;//初始化 
	int ans=-1e9;
	for(int i=1;i<=m;++i)
	{
		dp1[i]=max(dp1[i-1],0)+s[i];
		dp2[i]=max(dp2[i-1],dp1[i-1])+t[i];
		dp3[i]=max(dp3[i-1],dp2[i-1])+s[i]; 
		ans=max(ans,dp3[i]);//更新答案 
	}
	printf("%d\n",ans);
	return 0;
}