3357번: Monument

https://www.acmicpc.net/problem/3357


$O(pqr)$

다음 두 문제의 아이디어를 조합하면 풀 수 있다.
(1) http://codedoc.tistory.com/723
(2) http://codedoc.tistory.com/911

(x,y,z)상에 0 혹은 1이 주어졌을 때 1로만 이루어진 a*a*b꼴 직육면체 중 최대 4ab를 구해보자.
편의상 xy평면과 직육면체의 정사각형인 밑면과 평행하다고 하자.
푼 다음 직육면체를 적절히 돌려 나머지 방향에서도 똑같이 풀면 될 것이다.
먼저, 각 (x,y,z)마다 해당 지점을 끝점으로 하는 (1...x,1...y,z)상의 가장 큰 정사각형 한 변 길이를 구해놓는다. ... (2)
(x,y,1...i...z)에서 (x,y,i)의 최대 정사각형 한 변 길이를 a[i]라 하고 이들로 이루어진 히스토그램상에서 최대 직사각형 넓이를 구한다. ... (1)
이렇게 하면 (x,y,1...z)가 직육면체의 끝점이 되는 (1...x,1...y,1...z) 상의 직육면체 최대 ab가 구해진다.
모든 x,y에 대해 똑같이 풀고 최대 4ab를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int a[3], p[3] = { 0,1,2 }, pi[3], c[3], dp[151][151][151], stk[151], top, r;
char s[151][151][152];
int main() {
    scanf("%d%d%d", a + 1, a, a + 2);
    for (int i = 1; i <= a[0]; i++) for (int j = 1; j <= a[1]; j++) scanf("%s", s[i][j] + 1);
    do {
        for (int i = 0; i < 3; i++) pi[p[i]] = i;
        for (int i = 1; i <= a[p[0]]; i++) {
            for (int j = 1; j <= a[p[1]]; j++) {
                for (int k = 1; k <= a[p[2]]; k++) {
                    c[pi[0]] = i; c[pi[1]] = j; c[pi[2]] = k;
                    int n = s[c[0]][c[1]][c[2]] == 'N';
                    dp[i][j][k] = (min({ dp[i - 1][j][k], dp[i][j - 1][k], dp[i - 1][j - 1][k] }) + 1)*n;
                    while (dp[i][j][stk[top]]>dp[i][j][k]) r = max(r, (k - 1 - stk[top - 1])*dp[i][j][stk[top--]]);
                    stk[++top] = k;
                }
                while (top) r = max(r, (a[p[2]] - stk[top - 1])*dp[i][j][stk[top--]]);
            }
        }
    } while (next_permutation(p, p + 3));
    printf("%d", 4 * r);
    return 0;
}