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 <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 3010
using namespace std ;
int read() {
    int x = 0 , f = 1 ; char s = getchar() ;
    while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;}
    while(s <='9' && s >='0') {x = x * 10 + (s-'0'); s = getchar() ;}
    return x*f ;
}
int a[maxn][maxn] , Left[maxn][maxn] , Right[maxn][maxn] , up[maxn][maxn] ;
int n , m , ans1 , ans2 ;
int main () {
    n = read() , m = read() ;
    for(int i = 1 ; i <= n ; i ++) {
        for(int j = 1 ; j <= m ; j ++) {
            a[i][j] = read() ;
            Left[i][j] = j,Right[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]) {
                Left[i][j] = Left[i][j-1] ;
            }
        }
    }
    for(int i = 1 ; i <= n ; i ++) {
        for(int j = m - 1 ; j > 0 ; j --) {
            if(a[i][j] != a[i][i+1]) {
                Right[i][j] = Right[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]) {
                Left[i][j] = max(Left[i][j],Left[i-1][j]) ;
                Right[i][j] = min(Right[i][j] , Right[i-1][j]) ;
                up[i][j] = up[i-1][j] + 1 ;
            }
            int a = Right[i][j] - Left[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) ;
    return 0 ;
} 

完结吧....

洛谷P1169 棋盘制作

原文：https://www.cnblogs.com/lyt020321/p/11372824.html