HDU 1505 City Game：01 矩陣最大全 1 子矩陣 (直方圖 + 單調棧 O(nm))

問題

M×N 矩陣 (M,N≤1000)，'F' 為空地，'R' 為障礙。求最大全 'F' 子矩陣面積，租金 = 面積 × 3。

經典轉化：逐行構建直方圖高度

對每行 i，計算 h[i][j] = 以 (i,j) 為底向上連續 'F' 的數量。則第 i 行對應一個直方圖，求直方圖最大矩形面積即為以第 i 行为底的最大全 F 子矩陣。

直方圖最大矩形：單調棧 O(N)

對每行高度數組 h[1..N]：
維護遞增棧存索引。對每列 j：
- 彈出棧頂 tp 直到 h[tp] < h[j]，計算以 h[tp] 為高、寬度為 j - left[tp] - 1 的面積。
- left[j] = 棧頂索引 (左側第一個更低)。
同理從右向左求 right[j]。
面積 = h[j] * (right[j] - left[j] - 1)。

完整代碼 (優化版)

#include 
#include 
#include 
using namespace std;
const int MAXN = 1005;
int h[MAXN][MAXN], L[MAXN], R[MAXN];
char c;

int main() {
    int T; scanf("%d",&T);
    while (T--) {
        int n,m; scanf("%d%d",&n,&m);
        memset(h,0,sizeof h);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                scanf(" %c",&c);
                h[i][j] = (c=='F') ? h[i-1][j]+1 : 0;
            }
        }
        int ans = 0;
        for (int i=1;i<=n;i++) {
            // left
            for (int j=1;j<=m;j++) {
                L[j]=j;
                while (L[j]>1 && h[i][L[j]]<=h[i][L[j]-1]) L[j]=L[L[j]-1];
            }
            // right
            for (int j=m;j>=1;j--) {
                R[j]=j;
                while (R[j]

複雜度
O(nm) 時間，O(m) 額外空間 (滾動數組可優化 h 為一維)，n,m≤1000 時 1e6 操作極快。