Fancy的照片 && luoguP1387 最大正方形

﹏ヽ暗。殇╰゛Y 2023-06-01 15:54 17阅读 0赞

### Fancy的照片 ###

![nFEe1K.png][]

这道题在洛谷上有原题，但是洛谷上爆搜是可以过的，在模拟赛中最高得90。

[P1387 最大正方形][P1387]

模拟赛中的这道题目正解是一个\\(n^2\\)的\\(DP\\)，状态设\\(f\[i\]\[j\]\\)表示以\\((i,j)\\)这个点为右下角的最大正方形。

如果当前点合法

\\\[f\[i\]\[j\]=\\min(f\[i-1\]\[j\],f\[i-1\]\[j-1\],f\[i\]\[j-1\])+1\\\]

如果不合法

\\\[f\[i\]\[j\]=0\\\]

看图理解一下

![nFELuD.png][]

如果\\(f\[i\]\[j\]\\)从\\(f\[i-1\]\[j\]\\)转移过来，它必须满足\\(f\[i-1\]\[j-1\]\\)和\\(f\[i\]\[j-1\]\\)都大于等于\\(f\[i-1\]\[j\]\\)，才能满足正方形合法，综上所述，就是\\(\\min(f\[i-1\]\[j\],f\[i-1\]\[j-1\],f\[i\]\[j-1\])\\)，再加上当前的\\(1\\).

![nFZFRx.png][]

如果\\(f\[i-1\]\[j\]\\)是\\(2\\)黄色部分要想扩展为\\(3\\)需满足橙色部分\\(f\[i-1\]\[j-1\]\\)和红色部分\\(f\[i-1\]\[j\]\\)都大于等于\\(2\\)，才能满足正方形这个条件。

#include<iostream> #include<cstdio> using namespace std; const int N=3e3+100; int f[N][N]; bool mark[N][N]; int n,m; int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); mark[x][y]=1; } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (!mark[i][j]) f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1; else f[i][j]=0; int ans=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) ans=max(ans,f[i][j]); printf("%d\n",ans); return 0; }

转载于:https://www.cnblogs.com/last-diary/p/11450973.html

[nFEe1K.png]: /images/20230601/9812a52f370d408aa130a7fb10ca328b.png
[P1387]: https://www.luogu.org/problem/P1387
[nFELuD.png]: /images/20230601/2e0d9ce2d7e347dda91046de788ec267.png
[nFZFRx.png]: /images/20230601/48da3fe92d7e47e5883337fa5911b5e1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode-221. 最大正方形

目录题目思路动态规划动态规划(优化) 题目来源 [221. 最大正方形][221.] 题目思路现在我们

一时失言乱红尘/ 2024年03月23日 10:06/ 0 赞/ 148 阅读

相关 221. 最大正方形

打卡!!!每日一题今天继续给大家分享一道动态规划类型的题目，不过该题目的状态转移方程比较难以理解，我会详细的给大家分析一下题目描述： > 在一个由 ‘0’ 和 ‘1’

川长思鸟来/ 2023年10月11日 18:04/ 0 赞/ 57 阅读

相关 leetcode221 最大正方形

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nk

拼搏现实的明天。/ 2023年06月17日 04:58/ 0 赞/ 48 阅读

相关 Fancy的照片 && luoguP1387 最大正方形

Fancy的照片 ![nFEe1K.png][] 这道题在洛谷上有原题，但是洛谷上爆搜是可以过的，在模拟赛中最高得90。 [P1387 最大正方形][P1387]

﹏ヽ暗。殇╰゛Y/ 2023年06月01日 15:54/ 0 赞/ 18 阅读

相关 221. 最大正方形

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1

小灰灰/ 2023年05月29日 15:27/ 0 赞/ 38 阅读

相关最大正方形(动态规划)

最大正方形难度中等在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例: 输入: 1 0 1

Dear 丶/ 2023年03月12日 12:25/ 0 赞/ 39 阅读

相关 221. 最大正方形

题目： [221. 最大正方形][221.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

爱被打了一巴掌/ 2023年03月04日 14:28/ 0 赞/ 72 阅读

相关 221最大正方形

一、前言标签：动态规划、栈运用、双指针。问题来源LeetCode 5 难度：中等。问题链接：[https://leetcode-cn.com/problems/

深藏阁楼爱情的钟/ 2023年02月28日 15:26/ 0 赞/ 53 阅读

相关 P1387 最大正方形

题目描述在一个n\m的只包含0和1的矩阵里找出一个不包含0的最大正方形，输出边长。输入输出格式输入格式：输入文件第一行为两个整数n,m（1<=n,

深碍√TFBOYSˉ_/ 2022年05月27日 06:15/ 0 赞/ 279 阅读

相关 LeetCode-221. 最大正方形

[221. 最大正方形][221.] 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例: 输入: 1 0 1 0

墨蓝/ 2022年01月27日 01:23/ 0 赞/ 267 阅读