二维DP get ！

· · 个人记录

世上本没有路，走的人多了，也便成了路。

我博本没有二维 DP ，做的题多了，也便从高维 DP 里分出来了

提高：

传送门

机智的思路

嗯，只要理解了对角线长度和边长有关

就可以把对角线状态进行转移了

就是这样吧，，，

int m,n,ans;
int a[MAXN][MAXN],DP[MAXN][MAXN];
int wide[MAXN][MAXN],high[MAXN][MAXN];

int main(void)
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&a[i][j]);
        if(!a[i][j])
        {
            wide[i][j] = wide[i][j-1]+1;
            high[i][j] = high[i-1][j]+1;
        }
        else
        {
            int W = wide[i][j-1];
            int H = high[i-1][j];
            DP[i][j] = min(DP[i-1][j-1],min(W,H))+1;
        }
        ans = max(ans,DP[i][j]);
    }
    //DP两遍，两条对角线嘛
    memset(wide,0,sizeof(wide));
    memset(high,0,sizeof(high));
    memset(DP  ,0,sizeof(DP  ));
    for(int i=1;i<=n;i++)
    for(int j=m;j> 0;j--)
    {
        if(!a[i][j])
        {
            wide[i][j] = wide[i][j+1]+1;
            high[i][j] = high[i-1][j]+1;
        }
        else
        {
            int W = wide[i][j+1];
            int H = high[i-1][j];
            DP[i][j] = min(DP[i-1][j+1],min(W,H))+1;
        }
        ans = max(ans,DP[i][j]);
    }
    printf("%d\n",ans);
    return 0;
}

最大子矩形问题1：

传送门

求一个最大子矩形，常用的方法有悬线法

想想一下有一根垂直的线在矩形中扫来扫去，

那么某个子矩形的面积就是线的长度（up）乘以这条线能到达的最左（Left）最右（Right）端，

这条线不但能拐弯（能拐弯的是蛇），所以左右端点要分别取每列的最大、小值。

char c;
int n,m,ans;
int map[MAXN][MAXN];
int Left[MAXN][MAXN],Right[MAXN][MAXN],up[MAXN][MAXN];

int main(void)
{
    memset(Right,0x3f,sizeof Right);
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin >> c;
        if(c == 'F') map[i][j] = 1;
    }
    for(int i=1;i<=n;i++)
    {
        int l = 0;
        int r = m+1;
        for(int j=1;j<=m;j++)
            if(map[i][j]) Left[i][j] = l;
            else
            {
                Left[i][j] = 0;
                l = j;
            }
        for(int j=m;j>0;j--)
            if(map[i][j])   Right[i][j] = r;
            else
            {
                Right[i][j] = m+1;
                r = j;
            }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        if(map[i][j])
        {
            up[i][j] = up[i-1][j]+1;
            Left[i][j] = max(Left[i][j],Left[i-1][j]);
            Right[i][j] = min(Right[i][j],Right[i-1][j]);
            ans = max(ans,(Right[i][j]-Left[i][j]-1)*up[i][j]);
        }
    cout << ans*3 << endl;
    return 0;
}

最大子矩形问题2：

传送门

关于正方形的面积：

找长或宽中较短的一个来算

int main(void)
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin >> map[i][j];
        Left[i][j] = Right[i][j] = j;
        up[i][j] = 1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j<=m;j++)
            if(map[i][j] != map[i][j-1]) Left [i][j] = Left [i][j-1];
        for(int j=m-1;j>0;j--)
            if(map[i][j] != map[i][j+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 && map[i][j]!=map[i-1][j])
        {
            up[i][j] = up[i-1][j]+1;
            Left [i][j] = max(Left [i-1][j],Left [i][j]);
            Right[i][j] = min(Right[i-1][j],Right[i][j]);
        }
        int a = (Right[i][j]-Left[i][j]+1);
        int h = up[i][j];
        ans1 = max(ans1,min(h*h,a*a));
        ans2 = max(ans2,a*h);
    }
    cout << ans1 << endl << ans2;
    return 0;
}

类悬线法：

传送门

由于本人比较蠢，找不到悬线法的题放在哪篇博客里了（也可能没写博客？忘了），这里找到一道类似悬线法的题，就暂且放到这篇博客里吧。

首先，这道题的不同之处在于它允许将一些障碍点包含近矩形，所以不能直接用悬线法。

这里，只记录一个点向左能到达的位置和向上能到达的位置， n^3 枚举右上和右下端点，总的思路就是找一个最大的合法边框,所以只需判断左上和右上端点有没有连通，并记录最左能到达的位置即可，如果不能连通，则记录当前位置为矩形左边界，继续往右跑。

int n,m,ans;
int Left[MAXN][MAXN],up[MAXN][MAXN];
char ch [MAXN][MAXN];

int main()
{
    cin >> n >> m;
    for(int i=1;i<=n;++i) cin >> (ch[i]+1);
    for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    if(ch[i][j] == '.')
    {
        if(j == 1)  Left[i][j] = 1;
        else        Left[i][j] = Left[i][j-1];
        if(i == 1)  up  [i][j] = 1;
        else        up  [i][j] = up[i-1][j];
    }
    else
    {
        Left[i][j] = j+1;
        up  [i][j] = i+1;
    }
    for(int i=1;i<=n;++i)
    for(int j=i;j<=n;++j)
    {
        int Mx=0,last=0;
        for(int k=1;k<=m;++k)
            if(up[j][k] <= i)
            {
                if(Left[i][k]<=last && Left[j][k]<=last) Mx = max(Mx,k-last+1);
                else last = k;
            }
        ans = max(ans,(j-i+1)*Mx);
    }
    cout << ans;
}