博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
luogu P1387 最大正方形
阅读量:5898 次
发布时间:2019-06-19

本文共 1037 字,大约阅读时间需要 3 分钟。

特别水一道题,还写错了。每行维护一个前缀和,枚举矩形的左上角,扫矩阵第一行的长度,然后看这个长度能向下维持几行。但是忘记考虑要向上也扫一下能维持几行,再求一个和的。因为可能1的长度是逐行递减的,下面的矩形可以向上延申。

1 #include 
2 #include
3 using namespace std; 4 int n,m,res; 5 int mp[110][110]; 6 int main() 7 { 8 scanf("%d%d",&n,&m); 9 for (int i = 1;i <= n;i++)10 for (int j = 1;j <= m;j++)11 scanf("%d",&mp[i][j]);12 for (int i = 1;i <= n;i++)13 for (int j = 1;j <= m;j++)14 mp[i][j] += mp[i][j - 1];15 for (int i = 1;i <= n;i++)16 for (int j = 1;j <= m;j++)17 {18 if (mp[i][j] - mp[i][j - 1] == 0) 19 continue;20 int o,k,t;21 for (o = j;mp[i][o + 1] > mp[i][o];o++);22 for (k = i;mp[k + 1][o] - mp[k + 1][j - 1] == o - j + 1;k++);23 for (t = i;mp[t - 1][o] - mp[t - 1][j - 1] == o - j + 1;t--);24 res = max(res,min(o - j,k - t) + 1);25 }26 printf("%d\n",res);27 return 0;28 }

 

转载于:https://www.cnblogs.com/iat14/p/10568116.html

你可能感兴趣的文章
mybatis学习之一 开发环境配置和接口编程
查看>>
SqlDataAdapter DataSet DataTable 详解
查看>>
Android Xutils 框架
查看>>
Puppet resource命令参数介绍(七)
查看>>
C#基础知识整理 基础知识(21) 委托(二)
查看>>
Android应用程序键盘(Keyboard)消息处理机制分析(16)
查看>>
Sysbench 0.5版安装配置
查看>>
统一沟通-技巧-11-Lync-联盟-无法-音频-远程桌面-传文件
查看>>
书摘—你不可不知的心理策略
查看>>
【博客话题】毕业——开始人生的艰苦历程
查看>>
2014.7.30-8.3日广大网友的提问解答(答问题的第2个工作周)
查看>>
Powershell管理系列(二十五)PowerShell操作之获取AD账号及邮箱信息
查看>>
android开发 更新升级安装到一半自动闪退
查看>>
Linux安装telnet
查看>>
linux 标准I/O (二)
查看>>
量子纠缠
查看>>
【高德地图API】从零开始学高德JS API(三)覆盖物——标注|折线|多边形|信息窗口|聚合marker|麻点图|图片覆盖物...
查看>>
IOS 消息机制(NSNotificationCenter)
查看>>
JAVA 设计模式 策略模式
查看>>
openstack nova修改实例路径,虚拟磁盘路径
查看>>