动态规划之悬线法

现在才开始写有关悬线法

我主要都是通过这大佬学的（我这里只有模板和题目）：https://www.cnblogs.com/Tony-Double-Sky/category/1335134.html

悬线法主要是用来求一个图里矩阵的最大面积

首先是预处理

    int n,m,ans=0;
    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=1;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;j>=1;j--)
    if(a[i][j] && a[i][j+1]) r[i][j]=r[i][j+1];
    for(int i=2;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(a[i][j]==a[i-1][j]==1)
        {
            l[i][j]=max(l[i][j],l[i-1][j]);
            r[i][j]=min(r[i-1][j],r[i][j]);
            up[i][j]=up[i-1][j]+1;
        }
        int s=min(up[i][j],(r[i][j]-l[i][j]+1))*min(up[i][j],(r[i][j]-l[i][j]+1));
        ans=max(ans,s);
    }