例.1 Luogu-P1387最大正方形
按如下复杂度来分析
- O(\(n^6\))
- O(\(n^5\))
- O(\(n^3\))
- O(\(n^2\log n\))
- O(n^2)
O(\(n^6\))
最朴素的暴力做法
即使用两重循环枚举左上角端点，再使用两重循环枚举右下角端点，在用两重循环遍历区间内的每一个点，统计个数
有一道题是Luogu-B3724，刚好就是使用六重循环解决，主要代码如下
O（n^5）
由于需要寻找的部分是一个正方形，所以可以不用枚举右下角端点，改用枚举边长，计算右下角位置
即右下角位置横坐标是左上角横坐标+边长-1，纵坐标一样计算
注意：由于右下角可能超出正方形边界，所以当超边界时要直接break，因为再往后会越超越大
O(n^3)
发现一个一个统计太耗费时间了，所以使用二维前缀和优化，注意边界
O(\(n^2\log n\))
在N^5是发现了一个长度的单调性：
如果长度短的不行，那么长的肯定不行
如果长的可以，那么一定还有更短的
所以二分长度
O(\(n^2\))
考虑DP
①定义状态：dp[i][j]:表示以(i,j)作为右下角的最长正方形边长
②答案：max(dp[i][j])
③状态转移方程
首先,(i,j)作为右下角，自己就要是1
对于每个(i,j)，从(i-1,j-1)直接扩散到(i,j)是不行的，因为还需要(i,j)上面的1数量与(i-i,j-1)相同，左边同理
左边与上面连续1的个数实际上就是上一个格子与左边一个格子的DP值
但是要找三个DP值共有的部分，所以取最小值
得出:
\(dp[i][j]=\min(\min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1)+1\)
④边界
dp[i]][j]=a[i][j]
P5732 【深基5.习7】杨辉三角
还是DP分析
①状态
dp[i][j]:杨辉三角第i行第j列的数
②答案
dp[i][j]
③方程
每个DP值就是他上面的与它左上方的DP和
dp[i][j]=dp[i-1][j-1]+dp[i-1][j]
④边界
每行第一个和最后一个是1
dp[i][1]=dp[i][i]=1;
练1 P1130 红牌
定义状态
dp[i][j]:让第i个小组去做第j个步骤，前j个步骤所需的时间最小值
答案
max{dp[i][n]}
方程
对于每一个步骤，可以让上一个小组做上一步或这个小组做上一步
即dp[i][j]=min(dp[i-1][j-1],dp[i][j-1])+a[i][j]
a[i][j]表示第i个小组做第j个步骤所需的时间
边界
每个小组做第一步的时间
dp[i][1]=a[i][1]