题目大意：给出一个矩阵，要求从中找到每一列都是不下降数列的最大子矩阵，输出它的大小。
寻找最大子矩阵问题一般用悬线法解决。设 $u_{i,j}$ 为点 $(i,j)$ 向上延伸的最大长度；$l_{i,j}$ 与 $r_{i,j}$ 是向左右延伸的最大长度。
我们可得，当 $a_{i-1,j} \le a_{i,j}$ 时,$u_{i,j} = u_{i-1,j}+1$。当两旁的 $u_{i,j-1}$ 与 $u_{i,j+1}$ 大于当前 $u$ 的时候，$l$ ， $r$可以向左右延伸。
AC代码:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <utility> #include <vector> #include <string> #include <vector> #include <queue> #include <map> #define INF 999999999 using namespace std; typedef long long ll; int t; int n,m; int a[2005][2005]; int l[2005][2005],r[2005][2005],u[2005][2005]; int read() { char c=getchar(); int n=0,f=1; while(c < ‘0‘ || c > ‘9‘) { c=getchar(); } while(c >= ‘0‘ && c <= ‘9‘) { n=10*n+c-‘0‘; c=getchar(); } return n; } int main() { t=read(); while(t--) { n=read(); m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=read(); l[i][j]=r[i][j]=j; u[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]) { u[i][j]=u[i-1][j]+1; } } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { while(l[i][j] > 1 && u[i][j] <= u[i][l[i][j]-1]) { l[i][j]=l[i][l[i][j]-1]; } } for(int j=m;j>=1;j--) { while(r[i][j] < m && u[i][j] <= u[i][r[i][j]+1] ) { r[i][j]=r[i][r[i][j]+1]; } } } int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ans=max(ans,(u[i][j]*(r[i][j]-l[i][j]+1))); } } cout<<ans<<endl; } }