TIOJ 1643：建築工程規劃

TIOJ 1643：建築工程規劃

題目大意：有一個 $N\times M$ 的矩陣，第 $i$ 行第 $j$ 列的數字是 $a_{i,j}$，想要選取一個子矩陣使得這個子矩陣面積最大，但是子矩陣裡最大和最小的數字不能相差超過 $L$。

解法：首先可以看 $[0, L], [L+1, 2L+1] ...$ 的相同區間內的最大子矩形，使用單調隊列維護，然後可以把區間向右移 $1$，變成 $[0, 0], [1, L + 1], [L + 2, 2L + 2]...$，依序下去，總共看 $L+1$ 次即可。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1005;

int N, M, L, ans;
int a[SIZE][SIZE], c[SIZE][SIZE], h[2][SIZE];

void cal() {
    FOR (i, 1, N) {
        FOR (j, 1, M) h[i & 1][j] = (c[i][j] != c[i - 1][j] ? 1 : h[!(i & 1)][j] + 1);
        vector<pair<int, int>> st;
        FOR (j, 1, M) {
            int pos = j;
            while (st.size() && h[i & 1][j] <= st.back().S) {
                pos = st.back().F;
                ans = max (ans, st.back().S * (j - pos));
                st.pop_back();
            }
            st.pb (pos, h[i & 1][j]);
            if (j == M || c[i][j] != c[i][j + 1]) {
                while (st.size()) {
                    ans = max (ans, st.back().S * (j - st.back().F + 1));
                    st.pop_back();
                }
            }
        }
    }
}

void solve() {
    cin >> N >> M >> L;
    FOR (i, 1, M) c[0][i] = -1;
    FOR (i, 1, N) FOR (j, 1, M) cin >> a[i][j];
    L++;
    FOR (t, 1, L) {
        FOR (i, 1, N) FOR (j, 1, M) c[i][j] = (a[i][j] + t) / L;
        cal();
    }
    cout << ans << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！