棋盘DP

T1:最大正方形

在一个n*m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。

先考虑暴力，枚举起点和边长，可以O(n^5)的解决这个问题。 稍作优化（这个优化第一次看见好像还是在初赛）

采用f[i][j]表示第i行前j个元素的前缀和。这样计算一个矩阵的元素和的复杂度可以降至O(n)。总复杂度可以降至O(n^4)。

再稍微优化优化

直接计算二维矩阵前缀和，预处理的复杂度为O(n^{2)，计算的复杂度为O(1)，总复杂度为O(n}3)。

再优化

对于边长其实可以不用枚举，而可以二分。明显它具有单调性。总复杂度降至O(logn*n^2)。

但是！！！

这些方法都不行。

不是复杂度太丑，就是代码太丑，这题。。。可以DP呀。

我们的时间复杂度很多浪费在了对不可能的矩形进行检查，应该意识到，只有自己是1的点才能参与构造矩形。我们只需尝试将这个点往其它方向扩展即可。考虑使用悬线法。

悬线法

用途：解决给定矩阵中满足条件的最大子矩阵。

做法：用一条线左右移动直到不满足约束条件或到达边界。

定义这几个东西：

left[i][j]//代表从(i,j)能到达的最左位置
right[i][j]//代表从(i,j)能到达的最右位置
up[i][j]//代表从(i,j)向上扩展最长长度.
CPP

然后先进行横向扩展

for (int i=1;i<=n;i++){
		for (int j=2;j<=m;j++){
			if(a[i][j]&&a[i][j-1])le[i][j] = le[i][j-1];
		}
	}
for (int i=1;i<=n;i++){
	    for (int j=m-1;j>=1;j--){
			if(a[i][j]&&a[i][j+1])ri[i][j] = ri[i][j+1];
		}
	}
CPP

再纵向扩展

for (int i=2;i<=n;i++){
		for (int j=1;j<=m;j++){
			if(a[i][j]&&a[i-1][j]){
			le[i][j] = max(le[i][j],le[i-1][j]);
			ri[i][j] = min(ri[i][j],ri[i-1][j]);
			up[i][j] = up[i-1][j]+1;
			}
		}
	}
CPP

最后统计答案

for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			int c = ri[i][j]-le[i][j]+1;
			int b = min(c,up[i][j]);
			ans = max(ans,b);
		}
	}
CPP

但是考虑这样一种情况。

按照我们的状态转移方程，我们求出的是黑色部分的面积。但若红色部分的面积更大我们岂不是漏解了？

img

不是的，红色部分的面积会被蓝色left，right数组还未更新的地方更新。

img

但是这题还可以优化。因为悬线法可以针对所有矩形，而此题只需正方形。所以我们不选择横向和纵向扩展，而是直接斜着扩展，这也是正方形棋盘dp中的常用方法。

定义f[i][j]表示以节点i,j为右下角，可构成的最大正方形的边长。

只有a[i][j]==1时，节点i,j才能作为正方形的右下角；

对于一个已经确定的f[i][j]=x，它表明包括节点i，j在内向上x个节点，向左x个节点扫过的正方形中所有a值都为1。

那么易得状态转移方程

if (a[i][j]==1) f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
CPP

完成后在所有f[i][j]中取max即可。

T2:棋盘制作

国际象棋是世界上最古老的博弈游戏之一，和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想，棋盘是一个8×8大小的黑白相间的方阵，对应八八六十四卦，黑白对应阴阳。

而我们的主人公小Q，正是国际象棋的狂热爱好者。作为一个顶尖高手，他已不满足于普通的棋盘与规则，于是他跟他的好朋友小W决定将棋盘扩大以适应他们的新规则。

小Q找到了一张由N×M个正方形的格子组成的矩形纸片，每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘，当然，他希望这个棋盘尽可能的大。

不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘（当然，不管哪种，棋盘必须都黑白相间，即相邻的格子不同色），所以他希望可以找到最大的正方形棋盘面积和最大的矩形棋盘面积，从而决定哪个更好一些。

于是小Q找到了即将参加全国信息学竞赛的你，你能帮助他么？

悬线法秒掉即可。