C++

二维动态规划——最大正方形与最大长方形

更新时间 二维动态规划——最大正方形与最大长方形有0条评论

最大正方形问题

题目：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

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~

你也可能喜欢

发表评论