P3135 [USACO16JAN]Fort Moo P

Link_Cut_Y · 2023-02-01 17:47:36 · 题解

比较奇怪的一道题。只要会爆搜就行。可以说是暴力碾标算吧。

题目大意

给定一个字符矩形 \mathrm{g}，其中 \texttt{.} 代表平地，\texttt{X} 代表沼泽。在矩形 \mathrm{g} 中找到一个面积最大的矩形，使得矩形的四条边所在的字符都不是 \texttt{X}。

题目分析

抱着试一试的心态，我们可以写一个搜索。

首先我们可以遍历矩形的左上角，再遍历矩形的右下角，判断四条边是否合法并统计答案。判断四条边是否合法可以用前缀和做到 \mathrm{O(1)} 的复杂度，总复杂度 \mathrm{O(n ^ 4)}。

当然这样的算法一定会超时。考虑进行剪枝。

• 首先，如果当前答案是 \mathrm{s}，当前枚举的矩形长是 \mathrm{x}。那么矩形宽一定要严格大于 \mathrm{\dfrac{s}{x}}。这样可以减少第二层循环量。

• 其次，如果当前矩形长已经覆盖了沼泽，后面枚举一定也会。应该直接剪掉。

于是就可以愉快的过题了。

代码示例

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++ )
#define rop(i, a, b) for (int i = (a); i < (b); i ++ )
#define dep(i, a, b) for (int i = (a); i >= (b); i -- )
#define dop(i, a, b) for (int i = (a); i > (b); i -- )

using namespace std;

using LL = long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;

const int N = 210;
int n, m, ans, g[N][N];
char ch[N];
int col[N][N], row[N][N];

void solve(int x, int y) {
    for (int tx = x; tx <= n; tx ++ ) {
        if (col[tx][y] - col[x - 1][y]) break;
        for (int ty = max(y, (int)ceil(ans / (tx - x + 1) + y - 1)); ty <= m; ty ++ ) {
            if (row[x][ty] - row[x][y - 1]) break;
            if (row[tx][ty] - row[tx][y - 1]) break;
            if (col[tx][ty] - col[x - 1][ty]) continue;
            ans = max(ans, (tx - x + 1) * (ty - y + 1));
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    rep(i, 1, n) {
        scanf("%s", ch + 1);
        rep(j, 1, m) g[i][j] = (ch[j] == 'X');
    }
    rep(i, 1, n) rep(j, 1, m)
        row[i][j] = row[i][j - 1] + g[i][j],
        col[i][j] = col[i - 1][j] + g[i][j];
    rep(i, 1, n) rep(j, 1, m) {
        if (g[i][j]) continue;
        solve(i, j);
    }
    printf("%d\n", ans);
    return 0;
}

说在最后

真的没有想到暴力可以碾压标算。

纪念一下通过各种卑鄙巧妙的方法卡到的最优解。希望可以加强数据。