既然要求最大01子矩阵,那么把应该为0的位置上的数取反,这样就变成求最大子矩阵
最大子矩阵可以用单调栈
#include<stdio.h> #include<string.h> #include<algorithm> #define maxn 2005 using namespace std; int n,m,map[maxn][maxn],ans1,ans2,l[maxn],r[maxn],d[maxn],t; int main(){ scanf("%d%d", &n, &m); ; i<=n; i++) ; j<=m; j++){ scanf("%d", &map[i][j]); ) map[i][j]^=; } ; i<=n; i++){ //黑为奇数行列 ; j<=m; j++){ l[j]=r[j]=j; if (map[i][j]) d[j]++; ; } ; j<=m; j++) ]>=d[j]) l[j]=l[l[j]-]; ; j--) ]>=d[j]) r[j]=r[r[j]+]; ; j<=m; j++){ t=min(d[j],r[j]-l[j]+); ans1=max(ans1,t*t); ans2=max(ans2,d[j]*(r[j]-l[j]+)); } } memset(d,,sizeof(d)); ; i<=n; i++){ //白为奇数行列 ; j<=m; j++){ l[j]=r[j]=j; if (!map[i][j]) d[j]++; ; } ; j<=m; j++) ]>=d[j]) l[j]=l[l[j]-]; ; j--) ]>=d[j]) r[j]=r[r[j]+]; ; j<=m; j++){ t=min(d[j],r[j]-l[j]+); ans1=max(ans1,t*t); ans2=max(ans2,d[j]*(r[j]-l[j]+)); } } printf("%d\n%d\n", ans1, ans2); ; }
bzoj1057: [ZJOI2007]棋盘制作--最大子矩阵的更多相关文章
-
BZOJ1057 [ZJOI2007]棋盘制作(极大化思想)
1057: [ZJOI2007]棋盘制作 Time Limit: 20 Sec Memory Limit: 162 MB Submit: 1848 Solved: 936 [Submit][Sta ...
-
BZOJ1057 [ZJOI2007]棋盘制作 【最大同色矩形】
1057: [ZJOI2007]棋盘制作 Time Limit: 20 Sec Memory Limit: 162 MB Submit: 3248 Solved: 1636 [Submit][St ...
-
BZOJ1057 [ZJOI2007]棋盘制作
Description 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋.象棋以及日本的将棋同享盛名.据说国际象棋起源 于易经的思想,棋盘是一个8*8大小的黑白相间的方阵,对应八八六十四卦,黑白对应 ...
-
洛谷 P1169||bzoj1057 [ZJOI2007]棋盘制作
洛谷P1169 bzoj1057 这个题目跟最大全0子矩阵是类似的.正方形的话,只要把任意极大子正方形(”极大“定义见后面的”论文“)当成把某个极大子矩形去掉一块变成正方形即可,容易解决. 解法1:看 ...
-
BZOJ1057[ZJOI2007]棋盘制作 [单调栈]
题目描述 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋.象棋以及日本的将棋同享盛名.据说国际象棋起源于易经的思想,棋盘是一个8*8大小的黑白相间的方阵,对应八八六十四卦,黑白对应阴阳. 而我们的 ...
-
bzoj1057: [ZJOI2007]棋盘制作(悬线法)
题目要求纵横坐标和奇偶性不同的点取值不同,于是我们把纵横坐标和奇偶性为1的点和0的点分别取反,就变成经典的最大全1子矩阵问题了,用悬线法解决. #include<iostream> #in ...
-
【单调栈 动态规划】bzoj1057: [ZJOI2007]棋盘制作
好像还有个名字叫做“极大化”? Description 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋.象棋以及日本的将棋同享盛名.据说国际象棋起源 于易经的思想,棋盘是一个8*8大小的黑白相间的 ...
-
bzoj1057: [ZJOI2007]棋盘制作 [dp][单调栈]
Description 国际象棋是世界上最古老的博弈游戏之一,和中国的围棋.象棋以及日本的将棋同享盛名.据说国际象棋起源 于易经的思想,棋盘是一个8*8大小的黑白相间的方阵,对应八八六十四卦,黑白对应 ...
-
2018.10.19 bzoj1057: [ZJOI2007]棋盘制作(悬线法)
传送门 悬线法板题. 如果只求最大矩形面积那么跟玉蟾宫是一道题. 现在要求最大正方形面积. 所以每次更新最大矩形面积时用矩形宽的平方更新一下正方形答案就行了. 代码: #include<bits ...
随机推荐
-
jQuery选择器总结
jQuery 的选择器可谓之强大无比,这里简单地总结一下常用的元素查找方法 $("#myELement") 选择id值等于myElement的元素,id值不能重复在文档中 ...
-
JS打开新窗口的2种方式
1.超链接<a href="http://www.jb51.net" title="脚本之家">Welcome</a> 等效于js代码 ...
-
从一次面试经历谈PHP的普通传值与引用传值以及unset
关于这个概念一般都会在PHP的第一堂课说变量的时候给介绍,并且我以前还给其他PHPer介绍这个概念.但是作为一个工作一段时间的PHPer的我,竟然在面试的时候一下子拿不定主意最后还答错了,很觉得丢脸( ...
-
打开和创建SqlCe(.sdf文件)
打开SqlCe的工具有些少,目前能看到Vs2010安装插件之后打开.sdf文件 [转载]https://weblogs.asp.net/scottgu/vs-2010-sp1-and-sql-ce 需 ...
-
windows linux—unix 跨平台通信集成控制系统----系统硬件信息获取
控制集成系统需要了解系统的各项硬件信息,之前我们设计的时候,习惯使用c函数来搞,后来可能发现程序的移植性收到了一些影响,比如unix内核的一些c函数在linux下面是没有的: 比如 苹果达尔文内核的如 ...
-
vim资源
1.http://vimcasts.org vim技巧,还有一个高达120美元的课程 目前,正在看http://vimcasts.org/blog/2013/02/habit-breaking-hab ...
-
洗礼灵魂,修炼python(60)--爬虫篇—httplib2模块
这里先要补充一下,Python3自带两个用于和HTTP web 服务交互的标准库(内置模块): http.client 是HTTP协议的底层库 urllib.request 建立在http.clien ...
-
[BeiJing2006]狼抓兔子
题面 一眼看就是最小割板子题,建图也很直观,注意每一条边建双向边其实不用建4条边,只要反向边的容量和正边相同就行.然后直接跑最大流板子就行.不过此题拿vector存图会MLE……而拿链前存图就能卡过去 ...
-
通过beego快速创建一个Restful风格API项目及API文档自动化(转)
通过beego快速创建一个Restful风格API项目及API文档自动化 本文演示如何快速(一分钟内,不写一行代码)的根据数据库及表创建一个Restful风格的API项目,及提供便于在线测试API的界 ...
-
4-1:实现tee命令
#include <stdio.h> #include <sys/stat.h> #include <fcntl.h> #include <unistd.h& ...