• 「单调栈」城市游戏(玉蟾宫)


    城市游戏(玉蟾宫)

    原题链接:城市游戏

    题目大意

    给你(n imes m)个格子,每个格子上有'R'或'F',现在要找一块矩形土地,使这片土地都标有'F'且面积最大,让你求出这个最大面积并( imes3)输出

    题目题解

    面积最大,且为矩形,爆搜可以考虑一下,但爆搜肯定是超时的(话说有些题库(n^3)竟然能过?!),在爆搜的时候我们能得到的一个信息就是,如果以某一高度开始搜的话,所形成的矩形一定是以这一高度为最高高度的矩形,那这个问题就很简单了,可以类比到我们的单调栈来解决,但是很明显,这个题不能直接在二维上进行单调栈,因为有些地方是被分割了的,那这样明显不能构成我们的连续矩阵,那怎样来考虑呢?可以采用我们之前在二叉堆中学到的知识 分组

    将每一行分成一组,然后进行考虑,下一行由上一行的状态进行遗传,那么这样就能够得到我们的最终答案了,详细见代码

    //#define fre yes
    
    #include <cstdio>
    #include <iostream>
    
    const int N = 1005;
    int Stack[N], length[N], w[N];
    int Map[N][N];
    
    long long ans;
    int n, m;
    
    void work(int d[]) {
        int p = 0;
        w[p] = 0; Stack[p] = 0;
        for (int i = 1; i <= m + 1; i++) {
            if(d[i] > Stack[p]) {
                Stack[++p] = d[i];
                w[p] = 1;
            } else {
                int len = 0;
                while(Stack[p] > d[i]) {
                    len += w[p];
                    ans = std::max(ans, (long long)len * Stack[p]);
                    p--;
                } Stack[++p] = d[i]; w[p] = len + 1;
            }
        }
    }
    
    int main() {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char c[3];
                scanf("%s", c + 1);
                if(c[1] == 'F') Map[i][j] = Map[i - 1][j] + 1;
            } Map[i][m + 1] = 0;
        } 
        
        for (int i = 1; i <= n; i++) {
            work(Map[i]);
        } printf("%lld
    ", ans * 3);
    }
    
  • 相关阅读:
  • 原文地址:https://www.cnblogs.com/Nicoppa/p/11541085.html
  • 最新文章
  • 热门文章
一二三 - 开发者的网上家园