本来以为之前写过这个方法，今天又考了一道模板题，于是就记录一下
悬线法是求解一类极大子矩阵问题的DP解法（maybe）
例题：给一个01矩阵，求最大的一个子矩阵，使得该子矩阵全为1
考试有人想出了(O(n^2log^2n))的二分套二分做法，在此表示膜拜（即二分面积，枚举面积的约数）
从暴力方面想，对于一个点，直接求出它向左右上的最远距离再乘起来可能不对，所以只能求其中一个的最远距离
具体来说，定义(u_{i,j})表示从((i,j))向上走能走出的最远距离，(l,r)必须受到(u)的约束，所以定义为满足(u)最大，矩阵合法的条件下可以向左/右走到的最远点，那么(ans=max(u_{i,j}*(r_{i,j}-l_{i,j}+1)))
形象来看，可以理解为以((i,j))这个点为下端的连续的1组成的一根竖线，这根线左右移动所形成的矩形区域即这个点对应的矩形，这些矩形面积的最大值即为答案
显然(u,l,r)三个数组可以(O(n^2))递推（见代码），正确性：1.由上面的定义可知，所有的矩阵合法（是子矩阵） 2.最大的矩阵中一定存在一根等于矩形高度的悬线（该线可以左右移动形成该矩阵），如果不存在，即所有的悬线都比该矩阵高，那显然它不是最大矩阵
Code
#include<bits/stdc++.h>
#define N 1005
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int n,m,a[N][N],ans;
int up[N][N],l[N][N],r[N][N];
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
int main()
{
read(n);read(m);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
read(a[i][j]);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
{
if(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>=1;--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-1][j]&&a[i][j])
{
up[i][j]=up[i-1][j]+1;
l[i][j]=Max(l[i][j],l[i-1][j]);
r[i][j]=Min(r[i][j],r[i-1][j]);
}
ans=Max(ans,(r[i][j]-l[i][j]+1)*up[i][j]);
}
}
cout<<ans<<endl;
return 0;
}