hdu1505City Game(扫描线)
2024-10-16 08:49:53
http://acm.hdu.edu.cn/showproblem.php?pid=1505
题意:R为被占位置,F为空位,求出最大子空矩阵大小*3.
思路:1、悬线法,记录每个位置的悬线能到达的左边和右边最远位置。然后维护面积最大值。
每个点计算一次。
这是我第一个扫描法的题,从上由下扫描,up[i][j],le[i][j],r[i][j]表示格子i,j的悬线长度及该悬线向左、向右运动的“运动极限”。
我A的时候没怎么感觉它是扫描线的方法,有点背包的感觉。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int map[][];
int up[][];
int le[][];
int r[][];
int main()
{
int T,n,m,sum;
char ch;
scanf("%d",&T);
while(T--)
{
sum=;
scanf("%d%d",&n,&m);
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
ch=getchar();
while(ch!='F'&&ch!='R')
ch=getchar();
map[i][j]=ch=='F'?:;
}
}
int lo,ro;
for(int i=;i<n;i++)
{
lo=-;
ro=m;
for(int j=;j<m;j++)
{
if(map[i][j]==)
{
up[i][j]=;
le[i][j]=;
lo=j;
}
else if(map[i][j]==)
{
up[i][j]=i==?:up[i-][j]+;
le[i][j]=i==?lo+:max(lo+,le[i-][j]);
}
}
for(int j=m-;j>=;j--)
{
if(map[i][j]==)
{
r[i][j]=m;
ro=j;
}
else
{
r[i][j]=i==?ro-:min(ro-,r[i-][j]);
}
sum=max(sum,up[i][j]*(r[i][j]-le[i][j]+));
}
}
long long ans=(long long )sum*;
printf("%lld\n",ans);
}
return ;
}
最新文章
- GSM07.10协议中串口复用使用的校验算法
- pandas 学习(2): pandas 数据结构之DataFrame
- linux-shell笔记
- MySQL去除外键关联关系
- 思维 UVALive 3708 Graveyard
- HDU 3555 数位dp入门
- [HDOJ1160]FatMouse&#39;s Speed(DP)
- django admin site (三)
- 利用redis分布式锁的功能来实现定时器的分布式
- Eclipse创建Maven Web项目 + 测试覆盖率 + 常见问题(2015.07.14——湛耀)
- Cocopods -第三方库的管理
- node.js url模块
- BZOJ 1216: [HNOI2003]操作系统( 优先队列 )
- ACM网络镜像赛
- RESTful_简介
- JaveScript用二分法与普通遍历(冒泡)
- promise原理
- stm32之不定长接收
- 快速排序的java实现
- How to do sparse input text classification(dnn) using tensorflow
热门文章
- Malab 常用数学函数
- 一.jquery.datatables.js表格显示
- Esper学习之七:EPL语法(三)
- 【大数据系列】hadoop单机模式安装
- GDI+ 和GDI
- LeetCode 21 Merge Two Sorted Lists (有序两个链表整合)
- 部署OpenStack问题汇总(四)--openstack中nova-compute状态status显示为&#39;XXX&#39;的问题
- 备忘,commons-codec中可能用到的一些加密字符串的方法
- 【CF802C】Heidi and Library (hard) 费用流
- OpenCV学习笔记之课后习题练习3-4