HDU4328 Cut the cake（动规：最大子矩形问题/悬线法）

题目链接：传送门

题目大意：

　　给出N*M的字符矩阵（由字符B/R组成），求符合下图条件的子矩阵的最大周长。

　　1 ≤ N，M ≤ 1000。

思路：

　　悬线法。

#include <iostream>

#include <cstring>

#include <cstdio>

using namespace std;

const int MAX_N = 1e3 + ;

int N, M;

char mat[MAX_N][MAX_N];

int lef[MAX_N][MAX_N], rig[MAX_N][MAX_N], up[MAX_N][MAX_N];

void init1()

{

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= M; j++)

            if (j >  && mat[i][j] == mat[i][j-])

                lef[i][j] = lef[i][j-] + ;

            else

                lef[i][j] = ;

        for (int j = M; j >= ; j--)

            if (j < M && mat[i][j] == mat[i][j+])

                rig[i][j] = rig[i][j+] + ;

            else

                rig[i][j] = ;

    }

}

void init2()

{

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= M; j++)

            if (j >  && mat[i][j] != mat[i][j-])

                lef[i][j] = lef[i][j-] + ;

            else

                lef[i][j] = ;

        for (int j = M; j >= ; j--)

            if (j < M && mat[i][j] != mat[i][j+])

                rig[i][j] = rig[i][j+] + ;

            else

                rig[i][j] = ;

    }

}

int dp1()

{

    int ans = ;

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= M; j++) {

            if (i >  && mat[i][j] == mat[i-][j]) {

                up[i][j] = up[i-][j] + ;

                lef[i][j] = min(lef[i][j], lef[i-][j]);

                rig[i][j] = min(rig[i][j], rig[i-][j]);

            }

            else

                up[i][j] = ;

            int len = lef[i][j] + rig[i][j] - ;

            int high = up[i][j];

            ans = max(ans, *len+*high);

        }

    }

    return ans;

}

int dp2()

{

    int ans = ;

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= M; j++) {

            if (i >  && mat[i][j] != mat[i-][j]) {

                up[i][j] = up[i-][j] + ;

                lef[i][j] = min(lef[i][j], lef[i-][j]);

                rig[i][j] = min(rig[i][j], rig[i-][j]);

            }

            else

                up[i][j] = ;

            int len = lef[i][j] + rig[i][j] - ;

            int high = up[i][j];

            ans = max(ans, *len + *high);

        }

    }

    return ans;

}

int main()

{

    int T;

    int kase = ;

    cin >> T;

    while (T--) {

        cin >> N >> M;

        for (int i = ; i <= N; i++)

            for (int j = ; j <= M; j++)

                cin >> mat[i][j];

        int ans = ;

        init1();

        ans = max(ans, dp1());

        init2();

        ans = max(ans, dp2());

        printf("Case #%d: %d\n", kase++, ans);

    }

    return ;

}

/*

2

3 3

BBR

RBB

BBB

1 1

B

*/