放牧代码和思想
专注自然语言处理、机器学习算法

POJ 3494 Largest Submatrix of All 1’s​ 题解《挑战程序设计竞赛》

目录

rect.png挑战程序设计竞赛第二版.jpg

POJ 3494 Largest Submatrix of All 1’s 

最大子矩阵:给定M*N的01矩阵,求元素最多且都是1的子矩阵。

4.4常用技巧精选(二) 

栈 

还是先来跟书上的例题做个对比,借鉴思路。书上的矩形宽为1,底部对齐:

rect.png

在本题中,将每列中连续的1视作一个宽为1的矩形,就跟例题很像了,只不过底部没有对齐而已。如果我们逐行截断处理,则可视作底部对齐,则每一行构成的子问题都与例题完全一致,取子问题的最大解即为本题的解。

#include <iostream>

using namespace std;

#define MAX_N 2000 + 16
// 输入
int M, N;
int h[MAX_N];

int L[MAX_N], R[MAX_N];
int st[MAX_N];  // 栈

int solve()
{
    // 计算L
    int t = 0;  // 栈的大小
    for (int i = 0; i < N; i++)
    {
        while (t > 0 && h[st[t - 1]] >= h[i])
            t--;
        L[i] = t == 0 ? 0 : (st[t - 1] + 1);
        st[t++] = i;
    }

    // 计算R
    t = 0;
    for (int i = N - 1; i >= 0; i--)
    {
        while (t > 0 && h[st[t - 1]] >= h[i])
            t--;
        R[i] = t == 0 ? N : st[t - 1];
        st[t++] = i;
    }

    int res = 0;  // 注意防止溢出
    for (int i = 0; i < N; i++)
    {
        res = max(res, h[i] * (R[i] - L[i]));
    }
    return res;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (~scanf("%d%d", &M, &N))
    {
        int ans = 0;
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                int x;
                scanf("%d", &x);
                h[j] = x ? h[j] + 1 : 0;
            }
            ans = max(ans, solve());
        }
        printf("%d\n", ans);
    }

#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}
16474615 hankcs 3494 Accepted 192K 1625MS C++ 1193B 2017-01-14 09:35:55

又是一发入魂

例题、这题与《POJ 2082 Terrible Sets》可以构成一个系列,能够有效地训练观察力,直达不同问题的同一本质。

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 3494 Largest Submatrix of All 1’s​ 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机