【题解】洛谷 P7160 「dWoi R1」Sixth Monokuma's Son

wsyhb · 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;
}