uvalive 3029 City Game

时间:2022-09-22 16:25:23

https://vjudge.net/problem/UVALive-3029

题意:

给出一个只含有F和R字母的矩阵,求出全部为F的面积最大的矩阵并且输出它的面积乘以3。

思路:

求面积最大的子矩阵,可以用扫描线。参考训练指南(orz,虽然并不知道为什么用扫描线)。

对于每一个格子包含F,我们可以把它向上拉成一条悬线,直到上面的格子为R,然后观察这条悬线可以扫到左边与右边的最大距离,那么我们所求的面积就是所有的悬线中 悬线的长度乘以(右边界 - 左边界 + 1)的最大值。

然后,需要计算悬线的长度,用up来表示,那么当这个格子为F时up(i,j) = up(i - 1,j) + 1(i >= 1),up(i,j) = 1,(i == 0);

当这个格子为R时,up(i,j) = 0。

然后,用left数组和right数组维护左右边界的信息:

我们假设lo是当前格子之前的最近的是R的格子,从左往右遍历,那么 lo 的初值是-1,那么当(i,j) 为 F时 ,left(i,j) = max(left(i-1,j),lo + 1),为什么呢,因为当前的悬线如果是包含上一行此列的格子的话,那么就要考虑上一行左边的情况了;

当(i,j)为R时,left(i,j) = 0。

维护右边界的信息同理,不同的是求最小值和从右往左遍历。

!!!:记住一边遍历,一边维护。输入也是坑!

代码:

 #include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std; char a[][];
int up[][],right[][],left[][]; int main()
{
int t; scanf("%d",&t); while(t--)
{
int m,n; memset(a,,sizeof(a));
memset(up,,sizeof(up));
memset(right,,sizeof(right));
memset(left,,sizeof(left)); scanf("%d%d",&m,&n); getchar(); for (int i = ;i < m;i++)
for (int j = ;j < n;j++)
{
char s; s = getchar(); while (s != 'R' && s != 'F') s = getchar(); if (s == 'R') a[i][j] = ;
else a[i][j] = ;
} /*for (int i= 0;i < m;i++)
{
for (int j = 0;j < n;j++) printf("%d",(int)a[i][j]); printf("\n");
}*/ int ans = ; for (int i = ;i < m;i++)
{
for (int j = ;j < n;j++)
{
if (i == )
{
up[i][j] = a[i][j];
}
else
{
if (a[i][j]) up[i][j] = up[i-][j] + ;
else up[i][j] = ;
}
} int lo = -,ro = n; if (i == )
{
for (int j = ;j < n;j++)
{
if (a[i][j] == ) left[i][j] = , lo = j;
else left[i][j] = lo + ;
} for (int j = n - ;j >= ;j--)
{
if (a[i][j] == ) right[i][j] = n, ro = j;
else right[i][j] = ro - ;
} for (int j = ;j < n;j++)
{
int tmp = up[i][j] * (right[i][j] - left[i][j] + ); ans = max(ans,tmp * );
}
}
else
{
for (int j = ;j < n;j++)
{
if (a[i][j] == ) left[i][j] = , lo = j;
else left[i][j] = max(lo + ,left[i-][j]);
} for (int j = n - ;j >= ;j--)
{
if (a[i][j] == ) right[i][j] = n, ro = j;
else right[i][j] = min(ro - ,right[i-][j]);
} for (int j = ;j < n;j++)
{
int tmp = up[i][j] * (right[i][j] - left[i][j] + ); ans = max(ans,tmp * );
}
}
} /*for (int i = 0;i < m;i++)
{
for (int j = 0;j < n;j++)
{
printf("%d %d %d\n",up[i][j],left[i][j],right[i][j]);
}
}*/ printf("%d\n",ans);
} return ;
}

uvalive 3029 City Game的更多相关文章

  1. 【UVALive】3029 City Game(悬线法)

    题目 传送门:QWQ 分析 以前见到过差不多的这题. xhk说是单调栈水题,但我又不会单调栈,于是当时就放下了. 这么久过去了我还是不会用单调栈做这题,用的是悬线法. 非常好写 代码 #include ...

  2. City Game UVALive - 3029(悬线法求最大子矩阵)

    题意:多组数据(国外题好像都这样),每次n*m矩形,F表示空地,R表示障碍 求最大子矩阵(悬线法模板) 把每个格子向上延伸的空格看做一条悬线 以le[i][j],re[i][j],up[i][j]分别 ...

  3. UVALive 6889 City Park 并查集

    City Park 题目连接: http://acm.hust.edu.cn/vjudge/contest/view.action?cid=122283#problem/F Description P ...

  4. 并查集 - UVALive 6889 City Park

    City Park Problem's Link: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=129725 Mean: 在 ...

  5. LA 3029 City Game

    LA 3029 求最大子矩阵问题,主要考虑枚举方法,直接枚举肯定是不行的,因为一个大矩阵的子矩阵个数是指数级的,因此应该考虑先进行枚举前的扫描工作. 使用left,right,up数组分别记录从i,j ...

  6. LA 3029 - City Game (简单扫描线)

    题目链接 题意:给一个m*n的矩阵, 其中一些格子是空地(F), 其他是障碍(R).找一个全部由F 组成的面积最大的子矩阵, 输出其面积乘以3的结果. 思路:如果用枚举的方法,时间复杂度是O(m^2 ...

  7. UVa LA 3029 City Game 状态拆分,最大子矩阵O&lpar;n2&rpar; 难度&colon;2

    题目 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_pr ...

  8. UVaLive 3695 City Game &lpar;扫描线&rpar;

    题意:给定m*n的矩阵,有的是空地有的是墙,找出一个面积最大的子矩阵. 析:如果暴力,一定会超时的.我们可以使用扫描线,up[i][j] 表示从(i, j)向上可以到达的最高高度,left[i][j] ...

  9. UVaLive 6854 City &lpar;暴力&rpar;

    题意:给定一个 n*m 的矩阵,表示有多少条道路与它相连,其中有一个-1,表示未知,道路只能横着和竖着,求-1处的值. 析:根据题意可知,一个点,与其他周围的四个点都可能相连的,也就是说肯定有共用道路 ...

随机推荐

  1. *的JavaScript框架、库、工具及其使用

    几乎每隔一个星期,就有一个新的 JavaScript 库席卷网络社区!Web 社区日益活跃.多样,并在多个领域快速成长.想要研究每一个重要的 JavaScript 框架和库,是个不可能完成的任务.接下 ...

  2. EntityFramework 7 Join Count LongCount 奇怪问题(已修复)

    问题说明: 博客问题纪录 Use EF7, Linq Join Count is error EF7 Code Commit EF7 版本(注意 rc): 旧版本:"EntityFramew ...

  3. index&lpar;&rpar;、e&period;target&period;value、on&lpar;&rpar;与快捷处理的区别、

    <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title> ...

  4. Python的面向对象3

    接下来,我们接着讲Python的面向对象,在上一次的博客中,我们详细介绍了类与对象的属性,今天,我们来详细介绍一下面向对象中的方法! 1.定义实例方法 一个实例的私有属性就是以__开头的属性,无法被外 ...

  5. sass笔记-2&vert;Sass基础语法之让样式表更具条理性和可读性

    这一篇主要详述保持sass条理性和可读性的3个最基本方法--嵌套.导入和注释. 零. 变量 变量本身的作用是为了保持属性值的可维护性,把所有需要维护的属性值放在同一个地方,快速更改,处处生效,可谓售后 ...

  6. 一致性算法--Raft

    分布式一致性算法--Raft 前面一篇文章讲了Paxos协议,这篇文章讲它的姊妹篇Raft协议,相对于Paxos协议,Raft协议更为简单,也更容易工程实现.有关Raft协议和工程实现可以参考这个链接 ...

  7. 10、桥接模式(Bridge)

    桥接模式就是把事物和其具体实现分开,使他们可以各自独立的变化.桥接的用意是:将抽象化与实现化解耦,使得二者可以独立变化,像我们常用的JDBC桥DriverManager一样,JDBC进行连接数据库的时 ...

  8. Let&&num;39&semi;s-Bug修复日志

    Version 1.1 2015/11/16 修复了上传图片画质问题的Bug 修复了搜索功能的部分Bug 增加了下拉刷新的功能 修复了部分界面跳转之间的问题    

  9. VBScript开发Excel常见问题

    VBS基础 基本概念:VB & VBS & VBA VB.VBScript和VBA(Visual Basic For Application)这三种语言,既有联系又有区别.三种语言的语 ...

  10. 10-RabbitMQ-整合SpringBoot

    RabbitMQ整个SpringBoot SpringBoot因其配置简单.快速开发,已经成为热门的开发之一 消息中间件的工作过程可以用生产者消费者模型来表示.即,生产者不断的向消息队列发送信息 而消 ...