【第73题】继续刷动态规划，还学会了markdown的数学公式：棋盘制作

小码匠

发布于 2023-08-31 15:26:32

3620

发布于 2023-08-31 15:26:32

文章被收录于专栏：小码匠和老码农

题目

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P1169
- 参考题解：https://www.luogu.com.cn/problem/solution/P1169
标签：OI、动态规划、栈

题面

题目描述

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

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

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

输出 #1复制

4
6

说明/提示

对于20%的数据，N,M≤80

对于40%的数据，N*,*M≤400

对于100%的数据，N*,*M≤2000

正解

这是一个和名为悬线法的东西有关的题，给大家贴个链接https://oi-wiki.org/misc/hoverline/
先行奉上递推公式和一些基本释义

\left\{ \begin{array}{rcl} dp_{i, j}.left = & & {max(dp_{i,j}.left, dp_{i - 1, j}.left)}一开始本蒟蒻倒在了这里，需要注意的是这里dp_{i,j}表示的是区间，所以左端点最往里缩是取max\\ dp_{i, j}.right = & & {min(dp_{i,j}.right, dp_{i - 1, j}.right)}\\ dp_{i, j}.up = & & {dp_{i - 1, j}.left + 1}\\ \end{array} \right.

\left\{ \begin{array}{rcl} dp_{i, j}.left表示的是(i,j)对应悬线向左的最大宽度\\ dp_{i, j}.right表示的是(i,j)对应悬线向右的最大宽度\\ dp_{i, j}.up表示悬线长度，也是矩形的高度\\a表示的是宽度，b表示正方形的边长\\\end{array} \right.

由于up的存在，所以要考虑上一行啦

AC代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>

using namespace std;
#define endl '\n';


struct edge{
    int v, left, right, up;
};

void best_coder() {
    int n, m, ans_square = 0, ans_rectangle = 0;
    cin >> n >> m;
    vector<vector<edge>> dp(n + 1, vector<edge>(m + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> dp[i][j].v;
            dp[i][j].left = j;
            dp[i][j].right = j;
            dp[i][j].up = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 2; j <= m; ++j) {
            if (dp[i][j].v != dp[i][j - 1].v) {
                dp[i][j].left = dp[i][j - 1].left;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = m - 1; j > 0; --j) {
            if (dp[i][j].v != dp[i][j + 1].v) {
                dp[i][j].right = dp[i][j + 1].right;
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (dp[i][j].v != dp[i - 1][j].v) {
                dp[i][j].left = max(dp[i][j].left, dp[i - 1][j].left);
                dp[i][j].right = min(dp[i][j].right, dp[i - 1][j].right);
                dp[i][j].up = dp[i - 1][j].up + 1;
            }
            int a = dp[i][j].right - dp[i][j].left + 1;
            int b = max(0, min(a, dp[i][j].up));
            ans_square = max(ans_square, b * b);
            ans_rectangle = max(ans_rectangle, a * dp[i][j].up);
        }
    }
    cout << ans_square << endl;
    cout << ans_rectangle;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-08-03，如有侵权请联系 cloudcommunity@tencent.com 删除

markdown