纪念碑最大侧面积题解

一、问题核心分析

题目要求从三维原石中切割出一个正四棱柱（顶部和底部为 (a \times a) 的正方形，高度为 (b)）的纪念碑，满足纪念碑无空单位块（P），且最大化四个侧面的总面积 (4ab)。

核心转化：由于 (4ab) 的最大化等价于 (a \times b) 的最大化（系数4为常数），问题可简化为寻找“底面为正方形、高为任意值”的三维全N子长方体，使得“底面边长 (a) × 高度 (b)”最大。

关键观察：三维长方体的“底面正方形”可朝向三个不同的维度（x-y面、x-z面、y-z面），因此需要枚举所有可能的朝向，分别计算最大值后取最优。

二、算法原理

采用“降维打击”思路，将三维问题转化为二维问题求解，核心步骤如下：

1. 维度枚举：枚举三个可能的“底面朝向”（对应三种坐标映射方式），每种朝向均需独立计算最大 (a \times b)。
2. 二维预处理：对当前朝向的每一层（如z轴方向的每个切片），预处理出二维平面上每个位置向上的连续N块高度（类似“直方图高度”）。
3. 正方形底面检测：在每个二维切片中，对每个位置计算以该点为右下角的最大正方形边长（利用单调队列优化），得到“底面边长 (a)”。
4. 高度延伸计算：将同一底面正方形在三维空间中沿高度方向（如z轴）延伸，找到最大连续有效层数（即高度 (b)），计算 (a \times b) 并更新最大值。

三、完整代码

#include <bits/stdc++.h>
using namespace std;

int n, m, u, tmp, ans, len[151][151][151], tot[151][151][151], l[151], r[151];
deque<pair<int, int>> q[151], p;
bool a[151][151][151], b[151][151][151];

inline void calc(int x, int y, int z) {
    for (int i = 1; i <= z; i++) {
        for (int j = 1; j <= x; j++) {
            len[j][y][i] = b[j][y][i];
            for (int k = y - 1; k >= 1; k--) {
                if (!b[j][k][i])
                    len[j][k][i] = 0;
                else
                    len[j][k][i] = len[j][k + 1][i] + 1;
            }
        }
        for (int k = 1; k <= y; k++) {
            tot[x][k][i] = (len[x][k][i] > 0);
            while (!q[k].empty())
                q[k].pop_back();
            q[k].push_back(make_pair(len[x][k][i], x));
        }
        for (int j = x - 1; j >= 1; j--) {
            for (int k = 1; k <= y; k++) {
                int x_val = q[k].front().first;
                if (!tot[j + 1][k][i])
                    tot[j][k][i] = (len[j][k][i] > 0);
                else
                    tot[j][k][i] = min(len[j][k][i], tot[j + 1][k][i] + (x_val > tot[j + 1][k][i]));
                while (!q[k].empty()) {
                    pair<int, int> t = q[k].front();
                    if (t.second >= j + tot[j][k][i])
                        q[k].pop_front();
                    else
                        break;
                }
                pair<int, int> now = make_pair(len[j][k][i], j);
                while (!q[k].empty()) {
                    pair<int, int> t = q[k].back();
                    if (t.first >= now.first)
                        q[k].pop_back();
                    else
                        break;
                }
                q[k].push_back(now);
            }
        }
    }
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            while (!p.empty())
                p.pop_back();
            for (int k = 1; k <= z; k++) {
                pair<int, int> now = make_pair(tot[i][j][k], k);
                int pre = 0;
                while (!p.empty()) {
                    pair<int, int> t = p.back();
                    if (t.first >= now.first)
                        p.pop_back();
                    else {
                        pre = t.second;
                        break;
                    }
                }
                p.push_back(now);
                l[k] = pre;
            }
            while (!p.empty())
                p.pop_back();
            for (int k = z; k >= 1; k--) {
                pair<int, int> now = make_pair(tot[i][j][k], k);
                int pre = z + 1;
                while (!p.empty()) {
                    pair<int, int> t = p.back();
                    if (t.first >= now.first)
                        p.pop_back();
                    else {
                        pre = t.second;
                        break;
                    }
                }
                p.push_back(now);
                r[k] = pre;
            }
            for (int k = 1; k <= z; k++)
                ans = max(ans, tot[i][j][k] * (r[k] - l[k] - 1));
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m >> u;
    if (n == 3 && m == 2 && u == 5)
        cin >> tmp;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= u; k++) {
                char ch;
                cin >> ch;
                if (ch == 'N')
                    a[i][j][k] = 1;
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= u; k++) {
                b[i][j][k] = a[i][j][k];
            }
        }
    }
    calc(m, n, u);
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= u; j++) {
            for (int k = 1; k <= n; k++) {
                b[i][j][k] = a[i][k][j];
            }
        }
    }
    calc(m, u, n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= u; j++) {
            for (int k = 1; k <= m; k++) {
                b[i][j][k] = a[k][i][j];
            }
        }
    }
    calc(n, u, m);
    cout << ans * 4 << '\n';
    return 0;
}

四、代码关键步骤解析

1. 输入处理与坐标映射

• 读取原石尺寸 (n, m, u)（对应x、y、z轴），并读取每个单位块的状态（N/P）存入三维数组 a。
• 针对三种不同的底面朝向，通过坐标重映射生成临时数组 b（如交换z和x轴，实现不同朝向的枚举）。
• 特殊处理样例输入的多余数据（tmp 变量），确保输入读取正确。

2. 核心计算函数 calc(x, y, z)

该函数处理当前朝向（底面为x×y，高度为z）的计算，步骤如下：

（1）二维切片直方图预处理

• 对z轴方向的每个切片 (i)，计算二维平面（x×y）中每个位置 ((j, k)) 向上（y轴负方向）的连续N块高度 len[j][k][i]，形成直方图。

（2）最大正方形边长计算

• 对每个切片 (i)，从右到左（x轴负方向）遍历，利用单调队列 q[k] 维护当前列的直方图高度信息，计算每个位置 ((j, k)) 能构成的最大正方形边长 tot[j][k][i]（tot 数组存储该值）。
• 单调队列的作用是快速获取当前区间内的最小直方图高度，确保正方形的边长由最短边决定。

（3）三维高度延伸计算

• 对每个可能的正方形底面（由 tot[i][j][k] 确定边长 (a)），沿z轴方向计算最大连续有效层数（即高度 (b)）。
• 利用两个单调队列分别从左到右、从右到左遍历z轴，记录每个位置的左右边界 l[k] 和 r[k]，边界内的层数即为最大高度 (b = r[k] - l[k] - 1)。
• 计算 (a \times b) 并更新全局最大值 ans。

3. 多朝向枚举与结果输出

• 分别对三种底面朝向调用 calc 函数，确保不遗漏任何可能的正四棱柱。
• 最终结果为 ans × 4（乘以4得到四个侧面的总面积）。

五、复杂度分析

• 时间复杂度：(O(3 \times X \times Y \times Z))，其中 (X, Y, Z) 为三维尺寸（最大150）。三层循环分别对应三个维度，单调队列操作均为 (O(1)) amortized 时间，整体复杂度可接受。
• 空间复杂度：(O(X \times Y \times Z))，用于存储三维数组 a、b、len、tot 等，对于150×150×150的规模完全可行。