P1387 最大正方形

记录150#includebits/stdc.h using namespace std; const int N 105; int a[N][N]; // 存储原始矩阵 int dp[N][N]; // dp[i][j] 表示以 (i,j) 为右下角的最大正方形边长 int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; for(int i 1; i n; i) { for(int j 1; j m; j) { cin a[i][j]; } } //以 (i, j) 为右下角造一个更大的正方形。你的左边能延伸多远、上边能延伸多远、左上角能支撑多大的正方形这三者中最短的那块木板决定了你最终能造多大的正方形。这就是经典的“木桶效应”。 int ans 0; for(int i 1; i n; i) { for(int j 1; j m; j) { if(a[i][j] 1) { // 核心状态转移方程取左、上、左上三个方向的最小值 1 dp[i][j] min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) 1; // 实时更新全局最大边长 ans max(ans, dp[i][j]); } // 如果 a[i][j] 0dp[i][j] 默认为 0不需要处理 } } cout ans \n; return 0; } //min({a, b, c}) 这种写法是 C11 标准 引入的一个非常实用的语法糖叫做初始化列表题目传送门https://www.luogu.com.cn/problem/P1387前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的二维动态规划DP问题。问题转化状态定义在矩阵中寻找最大正方形最直接的思路是定义状态dp[i][j]为以坐标(i, j)作为右下角的全 1 正方形的最大边长。为什么一定要以(i, j)作为右下角呢因为这样我们在遍历矩阵时就可以利用已经计算好的左边、上边和左上角的信息通过递推公式得出当前点的状态。算法设计木桶效应/短板原理假设当前点a[i][j]是 1我们想要知道以它为右下角能构成的最大正方形边长。这取决于它左边的点(i-1, j)、上边的点(i, j-1)和左上角的点(i-1, j-1)能构成的正方形大小。这就好比“木桶效应”一个木桶能装多少水取决于最短的那块木板。同理以(i, j)为右下角的正方形边长取决于左、上、左上这三个相邻位置所能构成的正方形边长的最小值然后再加上当前点自身1。如果这三个方向中有一个方向是 0即无法构成正方形那么当前点最多也只能构成边长为 1 的正方形。代码分块详细解释1. 头文件、常量与状态数组定义#includebits/stdc.h using namespace std; const int N 105; int a[N][N]; // 存储原始矩阵 int dp[N][N]; // dp[i][j] 表示以 (i,j) 为右下角的最大正方形边长详细分析题目中 n,m≤100n,m≤100 所以将数组大小开到 105 足够。a[N][N]用来接收输入的 0/1 矩阵dp[N][N]用来存储动态规划的状态。因为全局数组默认会被初始化为 0这正好符合我们的需求如果a[i][j]是 0dp[i][j]保持为 0。2. 主函数与数据读入int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin n m; for(int i 1; i n; i) { for(int j 1; j m; j) { cin a[i][j]; } }详细分析标准的输入输出加速以及二维矩阵的读入。这里循环下标从 1 开始i1, j1是为了避免在状态转移时访问dp[i-1][j]等数组越界访问下标 0 时由于全局数组默认是 0刚好符合边界条件。3. 核心逻辑状态转移与全局更新// 以 (i, j) 为右下角造一个更大的正方形。你的左边能延伸多远、上边能延伸多远、左上角能支撑多大的正方形这三者中最短的那块木板决定了你最终能造多大的正方形。这就是经典的“木桶效应”。 int ans 0; for(int i 1; i n; i) { for(int j 1; j m; j) { if(a[i][j] 1) { // 核心状态转移方程取左、上、左上三个方向的最小值 1 dp[i][j] min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) 1; // 实时更新全局最大边长 ans max(ans, dp[i][j]); } // 如果 a[i][j] 0dp[i][j] 默认为 0不需要处理 } } cout ans \n; return 0; }详细分析这是代码的灵魂完美体现了动态规划的精髓。状态转移方程dp[i][j] min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) 1。如果当前格子是 1它试图向左、向上扩展。它能扩展的最大边长受限于它左方、上方、左上方这三个邻居中最“弱”的一个。取三者最小值后加 1就是以当前点为右下角的最大正方形边长。C11 语法糖代码中使用了min({...})这种初始化列表的写法这是 C11 引入的便捷语法可以直接求多个数的最小值避免了写两层嵌套的min函数。全局答案更新题目要求的是整个矩阵中的“最大正方形边长”而不是某个特定位置的。因此每计算出一个dp[i][j]我们就用ans max(ans, dp[i][j])来打擂台实时更新全局最大值。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点状态定义dp[i][j]记录以(i,j)为右下角的最大正方形边长将全局的“寻找最大正方形”问题拆解为每个局部格子的子问题边界处理下标从 1 开始遍历避免访问dp[i-1][j]时数组越界利用全局数组默认初始化为 0 的特性完美处理了矩阵的第一行和第一列状态转移min({左, 上, 左上}) 1运用“木桶效应”推导当前状态确保了以当前点为右下角构成的图形一定是一个完美的正方形条件判断if(a[i][j] 1)仅当当前格子为 1 时才进行转移如果当前格子是 0则无法作为任何全 1 正方形的右下角保持 dp 值为 0全局打擂台ans max(ans, dp[i][j])实时更新遍历过程中的最大边长保证了最终输出的ans是整个 n×m 矩阵中的全局最优解