文档章节

【bzoj3039】玉蟾宫

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 246
阅读 5
收藏 0

悬线法?

记录up表示往上延伸的F的高度
然后变成每行求最大子矩形面积

单调递增的栈,详见poj2082
(回宿舍睡觉有空补更)

顺带Orz DQS学长手速五分钟打完 + 提交 + 写题解Orz

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
const int MAXN = 1000 + 5;
char map[MAXN][MAXN];
int up[MAXN][MAXN];
int n,m;
struct dot
{
    int h,w;
};
void init()
{
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            up[i][j] = (up[i - 1][j] + 1) * (map[i][j] == 'F');
    return;
}
void scanf(char &c)
{
    c = getchar();
    while(!isalpha(c))
        c = getchar();
    return;
}
stack <dot> s;
int dpdpd()
{
    int ans = 0;
    for(int i = 1;i <= n;i ++)
    {
        for(int j = 1;j <= m;j ++)
        {
            int tmp = 0;
            while(!s.empty() && s.top().h > up[i][j])
            {
                tmp += s.top().w;
                ans = max(ans,s.top().h * tmp);
                s.pop();
            }
            s.push((dot){up[i][j],tmp + 1});
        }
        int tmp = 0;
        while(!s.empty())
        {
            tmp += s.top().w;
            ans = max(ans,s.top().h * tmp);
            s.pop();
        }
    }
    return ans;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
            scanf(map[i][j]);
    init();
    printf("%d\n",dpdpd() * 3);
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
三年色流风云回忆录:入行,迭代,不归(上)

写在前面:本文文章较长,可耐心阅读,内容旨在揭秘,请勿模仿。 一.色欲攻心,初次上当 玉临风已经大学毕业两年了,在这中间也找过几份工作,一个月拿着3500块钱的工资,还要忍受着上司的责...

卢松松博客
2018/07/16
0
0
英语muttonfatjade羊脂玉

羊脂玉英文(mutton fat jade) 中文名羊脂玉 外文名muttonfatjade 羊脂玉又称白玉,为软玉中之上品,极为珍贵。主要含有透闪石(95%)、阳起石和绿帘石。非常洁白,质地细腻,光泽滋润,状如凝...

tolearn
10/06
0
0
seajs初尝 加载jquery返回null解决学习日志

今天早上初尝seajs,发现一个非常蛋疼的事情,使用官方demo中的jquery是没有问题, 下载官方最新版jquery 2.1.1发现console.log($)返回null,百思不得其解!只能求助度娘! 在GitHub发现了玉...

尐桀
2014/10/31
557
1
jboot rpc 注册模式 和 直连模式

注册模式 和 直连模式 区别 注册模式 : 把所有标注 jbootrpcservice注解的service注册到consul中,一般运用玉 xxx -service的配置中 直连模式:直接与consul连接获取service对象调用,一般运...

atingFlye
2018/11/26
141
0
seajs如何整合jquery

转自:http://www.tuicool.com/articles/bmuaEb 今天早上初尝seajs,发现一个非常蛋疼的事情,使用官方demo中的jquery是没有问题, 下载官方最新版jquery 2.1.1发现console.log($)返回null,...

风一样的世界
2015/01/28
349
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring使用ThreadPoolTaskExecutor自定义线程池及实现异步调用

多线程一直是工作或面试过程中的高频知识点,今天给大家分享一下使用 ThreadPoolTaskExecutor 来自定义线程池和实现异步调用多线程。 一、ThreadPoolTaskExecutor 本文采用 Executors 的工厂...

CREATE_17
今天
5
0
CSS盒子模型

CSS盒子模型 组成: content --> padding --> border --> margin 像现实生活中的快递: 物品 --> 填充物 --> 包装盒 --> 盒子与盒子之间的间距 content :width、height组成的 内容区域 padd......

studywin
今天
7
0
修复Win10下开始菜单、设置等系统软件无法打开的问题

因为各种各样的原因导致系统文件丢失、损坏、被修改,而造成win10的开始菜单、设置等系统软件无法打开的情况,可以尝试如下方法解决 此方法只在部分情况下有效,但值得一试 用Windows键+R打开...

locbytes
昨天
8
0
jquery 添加和删除节点

本文转载于:专业的前端网站➺jquery 添加和删除节点 // 增加一个三和一节点function addPanel() { // var newPanel = $('.my-panel').clone(true) var newPanel = $(".triple-panel-con......

前端老手
昨天
8
0
一、Django基础

一、web框架分类和wsgiref模块使用介绍 web框架的本质 socket服务端 与 浏览器的通信 socket服务端功能划分: 负责与浏览器收发消息(socket通信) --> wsgiref/uWsgi/gunicorn... 根据用户访问...

ZeroBit
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部