洛谷P1169 棋盘制作
Dp - 悬线法
悬线法(好像)是可以解决给定矩阵中满足条件的最大子矩阵的样子
先就提论题
设个状态
设 f[i][j] 为从(i,j) 点扩展最多能达到的最左端的点
\(\color{red}{然后呢?}\)
设l[i][j] 为从(i,j) 点扩展能达到的最右端的点
\(\color{blue}{然后呢?}\)
设up[i][j] 为从(i,j)点能扩展到的上界
然后就是\(\color{green}{预处理}\)
从左往右扫 : f[i][j] = f[i][j-1] 从右往左扫 : l[i][j] = l[i][j+1]以上就是横向的情况,那么纵向的呢?
up[i][j] = up[i][j-1] r[i][j] = r[i-1][j] l[i][j] = l[i-1][j]综上的总代码
#include<bits/stdc++.h> #define maxn 2010 using namespace std ; int a[maxn][maxn] , l[maxn][maxn] , r[maxn][maxn] , up[maxn][maxn] ; int n , m , ans1 , ans2 ; int main() { cin >> n >> m ; for(int i = 1 ; i <= n ; i ++) { for(int j = 1 ; j <= m ; j ++) { cin >> a[i][j] ; l[i][j] = r[i][j] = j ; up[i][j] = 1 ; } } for(int i = 1 ; i <= n ; i ++) { for(int j = 2 ; j <= m ; j ++) { if(a[i][j] != a[i][j-1]) { l[i][j] = l[i][j-1] ; } } } for(int i = 1 ; i <= n ; i ++) { for(int j = m - 1 ; j > 0 ; j --) { if(a[i][j] != a[i][j+1]) { r[i][j] = r[i][j+1] ; } } } for(int i = 1 ; i <= n ; i ++) { for(int j = 1 ; j <= m ; j ++) { if(i > 1 && a[i][j] != a[i-1][j]) { l[i][j] = max(l[i][j],l[i-1][j]) ; r[i][j] = min(r[i][j],r[i-1][j]) ; up[i][j] = up[i-1][j] + 1; } int a = r[i][j] - l[i][j] + 1 ; int b = min(a,up[i][j]) ; ans1 = max(ans1,b*b) ; ans2 = max(ans2,a*up[i][j]) ; } } printf("%d\n%d",ans1,ans2); }