動态規劃之懸線法

現在才開始寫有關懸線法

我主要都是通過這大佬學的（我這裡隻有模闆和題目）：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);
    }