龍進最大正方形问题
题目：https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_A
现有HxW个边长为1的瓷砖拼在一起，其中一部分瓷砖有污迹，求仅由干净瓷砖构成的最大正方形的面积。
输入为1的代表有污迹，输入为0的代表没有污迹
Given a matrix (H × W) which contains only 1 and 0, find the area of the largest square matrix which only contains 0s.
Input
H W
c1,1 c1,2 ... c1,W
c2,1 c2,2 ... c2,W
:
cH,1 cH,2 ... cH,W
In the first line, two integers H and W separated by a space character are given. In the following H lines, ci,j, elements of the H × W matrix, are given.
Output
Print the area (the number of 0s) of the largest square.
Constraints
1 ≤ H, W ≤ 1,400
Sample Input
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0
Sample Output
4这题可以通过dp来解决，用数组dp[i][j]来表示以顶点(i,j)向左上角扩展，得到的最大正方形的边长。
分析知状态转移方程：
dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1
然后就敲代码就好了，这题不难。
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1405
int dp[MAXN][MAXN];
int square[MAXN][MAXN];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
for (int i = 1; i <= h; ++i)
{
for (int j = 1; j <= w; ++j)
cin >> square[i][j];
}
int ans = 0;
for (int i = 1; i <= h; ++i)
{
for (int j = 1; j <= w; ++j)
{
//当前方格有污渍
//cout << square[i][j] << endl;
if (square[i][j])
dp[i][j] = 0;
else
{
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
ans = max(ans, dp[i][j]);
}
}
}
cout << ans * ans << endl;
}最大长方形
最大长方形问题和上面的一题类似，只是要求最大的干净的长方形的面积。
这里可以利用直方图的思想，就是dp[i][j]存储的是当前点（包括）往上的矩形的信息。那么就能得到一个直方图。然后对这个进行检测就行了。
但是这同样有个问题，时间复杂度太高了。
于是我们可以借助栈来降低时间复杂度。本质上就是用栈来记录局部的解，然后提升速度。
栈中记录“仍有可能扩张的长方形的信息（记为rect）”。然后，在rect内又记录着长方形的高height以及其左端的位置pos。
首先我们在处理每一行的时候，先用dp把直方图给获取了，然后对直方图的每个值Hi，创建以Hi为高，左端pos为其坐标的长方形rect，然后执行以下操作：
- 如果栈为空
- 将rect压入栈
- 如果栈顶长方形高度<=rect的高
- 将rect压入栈
- 如果栈顶长方形的高大于rect的高
- 只要栈不为空，且栈顶长方形的高>=rect的高，就从栈中取出长方形，同时计算其面积并更新最大值。长方形的长等于“当前位置i”与之前记录的“左端位置pos”的差值
- 将rect压入栈，此时rect的左端位置pos为最后从栈中取出的长方形的pos值
题目：https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_B
Given a matrix (H × W) which contains only 1 and 0, find the area of the largest rectangle which only contains 0s.
Input
H W
c1,1 c1,2 ... c1,W
c2,1 c2,2 ... c2,W
:
cH,1 cH,2 ... cH,W
In the first line, two integers H and W separated by a space character are given. In the following H lines, ci,j, elements of the H × W matrix, are given.
Output
Print the area (the number of 0s) of the largest rectangle.
Constraints
1 ≤ H, W ≤ 1,400
Sample Input
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0
Sample Output
6代码：
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1405
bool square[MAXN][MAXN];
int dp[MAXN][MAXN];
struct rect
{
int pos;
int height;
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
for (int i = 1; i <= h; ++i)
{
for (int j = 1; j <= w; ++j)
cin >> square[i][j];
}
int ans = 0;
for (int i = 1; i <= h; ++i)
{
stack<rect> stk;
for (int j = 1; j <= w; ++j)
{
if (square[i][j])
{
dp[i][j] = 0;
}
else
{
dp[i][j] = dp[i - 1][j] + 1;
}
rect tmp;
tmp.pos = j;
tmp.height = dp[i][j];
if (stk.empty())
stk.push(tmp);
else
{
if (stk.top().height < tmp.height)
stk.push(tmp);
else if (stk.top().height > tmp.height)
{
int target;
while (!stk.empty() && stk.top().height > tmp.height)
{
auto x = stk.top();
stk.pop();
ans = max(ans, (tmp.pos - x.pos) * x.height);
target = x.pos;
}
tmp.pos = target;
stk.push(tmp);
}
}
}
//处理每行结尾处的长方形的问题
if (!stk.empty())
{
while (!stk.empty() && stk.top().height > 0)
{
auto x = stk.top();
stk.pop();
ans = max(ans, (w + 1 - x.pos) * x.height);
}
}
}
cout << ans << endl;
}转载请注明来源：https://www.longjin666.top/?p=987
欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~
