刷题记录:牛客NC20471[ZJOI2007]棋盘制作

棋盘制作"/>

刷题记录:牛客NC20471[ZJOI2007]棋盘制作

传送门:牛客

题目描述:

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。
据说国际象棋起源 于易经的思想，棋盘是一个8*8大小的黑白相间的方阵，对应八八六十四卦，黑白对应
阴阳。
而我们的主人公小Q， 正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规
则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由N*M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这
种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。
不过小Q还没有决定是找 一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相
间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决
定哪个更好一些。于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？
输入:
3 3
1 0 1
0 1 0
1 0 0
输出:
4
6

牛客网四星题,感觉思维难度挺大的.正解不易想到.但是掌握套路之后并不是一道难懂的题

主要思路:

1. 首先对于我们的每一个点,我们都可以先预处理出该点往左往右的最大的合法矩形的位置,使用 m a x _ l e f t 和 m a x _ r i g h t 数 组 来 存 储 max\_left和max\_right数组来存储 max_left和max_right数组来存储,并且我们是可以向上扩展的,因此我可以使用 u p _ l e n g t h 数 组 up\_length数组 up_length数组来记录我们的这个点向上扩展的长度.
2. 然后每一次都比较该行和上一行的左右扩展程度,取一个重叠的位置,进行操作

emmm,对于此题文字不易描述,重点将在代码中注释

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
#include <deque>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
int n,m;int max_left[2010][2010],max_right[2010][2010];
int up_lenght[2010][2010];int mp[2010][2010];
int main() {n=read();m=read();for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {mp[i][j]=read();//进行左右以及上方的初始化,显然左右扩展最小也是自己max_left[i][j]=j;max_right[i][j]=j;up_lenght[i][j]=1;}}for(int i=1;i<=n;i++) {for(int j=2;j<=m;j++) {if(mp[i][j]!=mp[i][j-1]) {//预处理左边的max_left[i][j]=max_left[i][j-1];}    }}for(int i=1;i<=n;i++) {for(int j=m-1;j>=1;j--) {if(mp[i][j]!=mp[i][j+1]) {//预处理右边的max_right[i][j]=max_right[i][j+1];}}}int ans1=-inf,ans2=-inf;for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {//此处我们发现i=1时显然是没有上一行的,但是我们是不能不记录第一行的值的//因为我们的最大贡献可能就是第一行,所以我们应该判断一下if(mp[i][j]!=mp[i-1][j]&&i>1) {//相对于左边,取max,相对于右边,则应该取min,感觉迷糊自己画一下max_left[i][j]=max(max_left[i][j],max_left[i-1][j]);max_right[i][j]=min(max_right[i][j],max_right[i-1][j]);//扩展我们的上方长度up_lenght[i][j]+=up_lenght[i-1][j];}//len代表水平的长度,因为是正方形,我们的边长应该取长宽较小的int len=max_right[i][j]-max_left[i][j]+1;ans1=max(ans1,min(len,up_lenght[i][j])*min(len,up_lenght[i][j]));ans2=max(ans2,len*up_lenght[i][j]);}}cout<<ans1<<endl<<ans2<<endl;return 0;
}

注意,假设有人看完了本代码,觉得有一些问题,因为我们进行记录每一个矩形的长宽直接是取最小的,比如下图

假设使用我们上述的算法的话遇到我们此时的j位置就是直接记录了红色矩形的面积,但是此时我们的黑色区间才是最大的,难道是算法错了??

但是此时我们想一下,我们的j位置的右边的位置和右边的上方的位置肯定相同的.如下图

因此此时我们其实是可以靠j位置的左边和右边记录我们的黑色矩形的值的