[ZJOI2007]棋盘制作

Time Limit:20000MS  Memory Limit:165536K
Total Submit:33 Accepted:23
Case Time Limit:10000MS

Description

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

Input

第一行包含两个整数N和M，分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵，表示这张矩形纸片的颜色（0表示白色，1表示黑色）。

Output

包含两行，每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积，第二行为可以找到的最大矩形棋盘的面积（注意正方形和矩形是可以相交或者包含 的）。

Sample Input

3 3
1 0 1
0 1 0
1 0 0

Sample Output

4
6

Hint

对于20%的数据，N, M ≤ 80
对于40%的数据，N, M ≤ 400
对于100%的数据，N, M ≤ 2000

Source

61.187.179.132:8080/JudgeOnline/showproblem
原来的算法是没有问题，但是写的太沙茶了。首先那玩意根本不是那么递推的，要用到类似单调队列的结构，一层层扫描过去，对每层维护交替的能向上延伸多少，然后用单调队列算出对于每个点来说，往左第一个高度小于它的和往右第一个小于它的同时注意交替性，然后更新答案就可以了。。
细节很要紧，WA了N次囧。。速度鬼慢但长度不到1K，(*^__^*)
更WS的是我原来那个错误的算法居然能过SPOJ上的数据天哪。。我被雷到了。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,MaxS=0,MaxR=0;
const int maxn=2000+10;
int Line[maxn]={0};
int H[maxn]={0};
void ReadLine()
{
int x;
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
if(x!=Line[i])H[i]++;
else H[i]=1;
Line[i]=x;
}
}
void Renew(int a,int b)
{
if(a>b) swap(a,b);
MaxS=max(MaxS,a*a);
MaxR=max(MaxR,a*b);
}
void CalLine()
{
static int L[maxn],R[maxn];
for(int i=1;i<=m;++i)
{
L[i]=i-1;
while(L[i]&&H[L[i]]>=H[i]&&Line[L[i]+1]!=Line[L[i]])
L[i]=L[L[i]];
}
for(int i=m;i>=1;–i)
{
R[i]=i+1;
while(R[i]<=m&&H[R[i]]>=H[i]&&Line[R[i]]!=Line[R[i]-1])
R[i]=R[R[i]];
}
for(int i=1;i<=m;i++) Renew(H[i],R[i]-L[i]-1);
}
int main()
{
scanf("%d %d",&n,&m);
rep(i,n)ReadLine(),CalLine();
cout<<MaxS<<endl<<MaxR<<endl;
}