[luogu]P1169 [ZJOI2007]棋盘制作[DP][单调栈]
[ZJOI]棋盘制作
——!x^n+y^n=z^n
题目描述
国际象棋是世界上最古老的博弈游戏之一,和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想,棋盘是一个8*8大小的黑白相间的方阵,对应八八六十四卦,黑白对应阴阳。
而我们的主人公小Q,正是国际象棋的狂热爱好者。作为一个顶尖高手,他已不满足于普通的棋盘与规则,于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由N*M个正方形的格子组成的矩形纸片,每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘,当然,他希望这个棋盘尽可能的大。
不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘(当然,不管哪种,棋盘必须都黑白相间,即相邻的格子不同色),所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积,从而决定哪个更好一些。
于是小Q找到了即将参加全国信息学竞赛的你,你能帮助他么?
输入输出格式
输入格式:
包含两个整数N和M,分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵,表示这张矩形纸片的颜色(0表示白色,1表示黑色)。
输出格式:
包含两行,每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积,第二行为可以找到的最大矩形棋盘的面积(注意正方形和矩形是可以相交或者包含的)。
输入输出样例
输入样例1#:
3 3
1 0 1
0 1 0
1 0 0
输出样例1#:
4
6
说明
对于20%的数据,N, M ≤ 80
对于40%的数据,N, M ≤ 400
对于100%的数据,N, M ≤ 2000
这题不难使人联想到最大正方形和玉蟾宫,于是我们先考虑化归,对于一个棋盘,我们会发现那些行列相间的格子(i+j必定奇偶性相)。
所以如果我们把(i,j)这个格子的颜色改变,不就是要求同色最大正方形和最大长方形面积吗?
对于第一问,我们用动态规划解决,对于第二问,我用的是单调栈,方法详见上一篇博文。
但据说luogu这题数据很水啊,心中不安...
代码:
//2017.10.30 //DP+单调栈 #include<iostream> #include<cstdio> #include<cstring> using namespace std; inline int read(); int Max(int x,int y){return x>y?x:y;} int Min(int x,int y){return x<y?x:y;} namespace lys{ ; int dp[N][N],s[N][N],a[N][N],s1[N],s2[N]; int n,m,top,ans2,ans1; void init(){ int i,j; ;i<=n;i++) ;j--) s[i][j]=a[i][j]?s[i][j+]+:; } void find(int row){ top=; int i,del; ;i<=n+;i++){ del=i; while(top&&s1[top]>=s[i][row]){ ans2=Max(ans2,s1[top]*(i-s2[top])); del=s2[top--]; } s1[++top]=s[i][row]; s2[top]=del; } } int main(){ int i,j; n=read(); m=read(); ;i<=n;i++) ;j<=m;j++){ a[i][j]=read(); ) a[i][j]^=; } ;i<=n;i++) ;j<=m;j++){ dp[i][j]=; ][j]&&a[i][j]==a[i][j-]&&a[i][j]==a[i-][j-]) dp[i][j]=Min(dp[i-][j-],Min(dp[i-][j],dp[i][j-]))+; ans1=Max(ans1,dp[i][j]); } init(); ;i<=m;i++) find(i); ;i<=n;i++) ;j<=n;j++) a[i][j]^=; init(); ;i<=m;i++) find(i); printf("%d\n%d\n",ans1*ans1,ans2); ; } } int main(){ lys::main(); ; } inline int read(){ ,ff=; char c=getchar(); '){ ; c=getchar(); } +c-',c=getchar(); return kk*ff; }
最新文章
- 修改安卓串口蓝牙app问题记录
- SQL各种连接查询详解(左连接、右连接..)
- MyEclipse10中导入的jquery文件报错(出现红叉叉,提示语法错误)
- 重点关注之自定义序列化方式(Protobuf和Msgpack)
- Codeforces Round #368 (Div. 2) D. Persistent Bookcase
- VB6-AppendToLog 通过API写入日志
- facebook分享遇到的错误解决方法
- Servlet的学习之Cookie
- 黄聪:Microsoft Enterprise Library 5.0 系列教程(三) Validation Application Block (高级)
- netty最快?
- NodeJS异步I/O解析
- 深入探索C++对象模型(四)
- Mac之OS系统下搭建JavaEE环境 <;五>; 之Mysql数据库的安装及配置
- MySQL 多表查询 学习与练习
- Java 程序员必须了解的 7 个性能指标
- git rewinding head to replay your work on top of it...
- 新浪SAE创建微信模板消息应用与SVN的使用
- 条件式变分自编码机(Conditional Variational Autoencoders)
- java面试:手写代码
- 关于BufferefReader.readLine()方法的理解
热门文章
- Android Studio 连接夜神模拟器
- HTTP response status
- XMind8激活为Pro教程 - Windows&;Mac
- JavaBean简介和要求
- 设计模式:单例模式(Singletion)
- [BZOJ4476] [JSOI2015] 送礼物 (01分数规划+ST表)
- 【CF321E】+【bzoj5311】贞鱼
- 2019 Multi-University Training Contest 1 - 1001 - Blank - dp
- R语言基础篇——数据读写
- MVC一个action对应多个视图的写法