[最大子矩阵问题 && 题解] Codevs 2491 玉蟾宫

Author Avatar
空気浮遊 2018年01月04日
  • 在其它设备中阅读本文章
  • 最大子矩阵
  • 题解
  • 分享到 Facebook
  • 分享到 Telegram
  • 分享到 Twitter
  • 分享到微博

Problem

传送门

Solution

为最大子矩阵的模板题。
使用悬线法。

论文还是看了不久的 orz 下面两篇是我找到稍微好看一点的。
论文名为王知昆编撰的《浅谈用极大化思想解决最大子矩形问题》。
Clove_unique - 转载
konjak 魔芋 - 转载(带了点稍微详细些的图)

也可以选择下载附件。这个文档也是从百度文库上弄下来的
浅谈用极大化思想解决最大子矩形问题.doc

说是最大子矩形问题,其实也可以应用到矩阵当中。如论文所说的,使用悬线法会更加恰当,并且非常简洁易懂。
注意有个小坑,就是你需要特判一下这玩意是不是障碍点。障碍点不应该进行枚举。如果上一个是障碍点,也不应该更新 L 或 R。
L 或 R 我认为应该事先预处理一下。

下方是代码 ww

// Code by ajcxsu
// Problem: Codevs P2491
#include<bits/stdc++.h>
using namespace std;

const int N=1010;
bool mz[N][N];
int H[N][N],L[N][N],R[N][N];

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    char ch;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            cin>>ch;
            mz[i][j]=(ch=='R');
        }
    for(int i=1;i<=n;i++){
        L[i][1]=1;
        for(int j=2;j<=m;j++)
            if(mz[i][j-1]) L[i][j]=j;
            else L[i][j]=L[i][j-1];
    }
    for(int i=1;i<=n;i++){
        R[i][m]=m;
        for(int j=m-1;j>=1;j--)
            if(mz[i][j+1]) R[i][j]=j;
            else R[i][j]=R[i][j+1];
    }
    int S=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            if(i!=1) {
                if(mz[i-1][j]) H[i][j]=1;
                else {
                    H[i][j]=H[i-1][j]+1;
                    L[i][j]=max(L[i][j],L[i-1][j]);
                    R[i][j]=min(R[i][j],R[i-1][j]);
                }
            }
            else H[i][j]=1;
            if(!mz[i][j]) S=max(S,(R[i][j]-L[i][j]+1)*H[i][j]);
        }
    cout<<S*3<<endl;
    return 0;
}

本文链接:https://pst.iorinn.moe/archives/sol_codevs_2491.html
许可: https://pst.iorinn.moe/license.html
若无特别说明,博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆

      新篇
旧篇      
    • fingerprint Login
  • home 主页
  • inbox 归档
    • December 2024 1
    • August 2024 1
    • June 2024 1
    • April 2024 3
    • March 2024 1
    • February 2024 2
    • January 2024 1
    • November 2023 1
    • August 2023 1
    • May 2023 1
    • February 2023 2
    • January 2023 2
    • July 2022 1
    • June 2022 1
    • April 2022 1
    • March 2022 1
    • February 2022 2
    • December 2021 1
    • November 2021 1
    • August 2021 3
    • July 2021 3
    • April 2021 2
    • March 2021 1
    • February 2021 4
    • January 2021 2
    • December 2020 1
    • November 2020 1
    • October 2020 3
    • September 2020 1
    • August 2020 1
    • July 2020 1
    • March 2020 1
    • December 2019 1
    • September 2019 1
    • July 2019 1
    • April 2019 2
    • March 2019 13
    • February 2019 15
    • January 2019 11
    • December 2018 3
    • November 2018 6
    • October 2018 28
    • September 2018 32
    • August 2018 19
    • July 2018 13
    • June 2018 27
    • May 2018 11
    • April 2018 12
    • March 2018 19
    • February 2018 8
    • January 2018 7
    • December 2017 2
    • November 2017 2
  • apps 分类
    • 笔记
    • 题解
    • 杂文
    • 技术
    • 游戏
    • 小说
  • 留言板
  • 关于
  • 友链
  • 文章总数 282
主题 - Material i
expand_less
Copyright © 2025 雪屋
Float in air.
Powered by Typecho
Theme - Material