土豪聪要请客 (stol)

众所周知, 聪哥 (ndsf) 是个土豪, 不过你们不知道的是他的 MZ 和他的 RMB 一样滴多……

某天土豪聪又赚了 \(10^{10000}\) 的 RMB, 他比较开心, 于是准备请客. 他在自己在 XX 星上的别墅里面大摆酒席, 想要邀请尽可能多的 MZ 来参加他的宴会. 他将会同 MZ 一起坐在一个巨大的长方形桌子上. 这个桌子能坐下的人数等于他的边长. 聪哥要求他的桌子能够放进他的别墅, 并且桌子的边必须与别墅的边界平行. 给定别墅的平面图, 请你求出聪哥最多可以请多少个 MZ.

输入格式

第一行 n, m. 表示别墅的长宽

下面 n 行, 每行 M 个字符, 表示一个方块是空的 (.) 或是被占用了 (X) .

聪哥只要他的桌子放在别墅里, 并且桌子不能占用任何一个已经占用了的方块.

输出格式

一个数, 表示聪哥最多可以请几个 Maze.

样例输入 1

2 2
..
..

样例输出 1

7

样例输入 2

4 4
X.XX
X..X
..X.
..XX

样例输出 2

9

数据范围

对于 60% 的数据,\(n, m \leq 100\) 对于 100% 的数据,\(n, m \leq 400\)

Explanation

当我第一次知道要做这道题的时候

其实我是, 是拒绝的

我跟导演讲, 我拒绝, 因为

其实我, 根本不会写 DP

教练跟我讲, 写完加特技

DP 上优化, 速度很高、很快、很 AC.

加了一行特技之后, 速度 DUANG~

后来我也知道暴力是, 是假的, 是 DP 成分的

我现在呢, 每天还在, 加特技

加了很多特技, 复杂度 DUANG~ DUANG~ DUANG~

考试用完后, 不加特技

AC 都没有

我的暴力, 速度特快

因为我, 用 DP

我用完之后, 根本没有写暴力

这个就是我用的 IDE

我的 IDE DP DP 上 DP

写的时候, 根本没有上暴力

AC AC, 我的代码, 会 AC

我的代码, 会 AC

是 DP 的暴力, 是暴力的 DP.

大概就是这个意思, 随便优化一下暴力搜索就当成 DP 在 170ms 以内 AC 了.

如果要转发上面那首打油诗请署上我的 handle, 谢谢.

Example Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 410;

int n, m;
bool used[maxn][maxn];
int extent_hor[maxn][maxn];
int extent_ver[2][maxn][maxn],
    ver_idx;

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            char ch = '\n';
            while (ch != '.' && ch != 'X')
                scanf("%c", &ch);
            used[i][j] = ch == 'X';
        }
    // Maximum extension -> right end
    for (int i = 1; i <= n; i++) {
        extent_hor[i][m + 1] = 0;
        for (int j = m; j >= 1; j--)
            if (used[i][j])
                extent_hor[i][j] = 0;
            else
                extent_hor[i][j] = extent_hor[i][j + 1] + 1;
    }
    // Maximum extension -> bottom end
    int final_res = 0;
    for (int i = n; i >= 1; i--) {
        int tmp_best = 0;
        for (int j = 1; j <= m; j++) {
            extent_ver[ver_idx][j][1] = extent_hor[i][j];
            if (!extent_ver[ver_idx][j][1])
                continue;
            tmp_best = max(tmp_best, extent_ver[ver_idx][j][1] + 1);
            for (int k = 2; k <= n + 1 - i; k++) {
                extent_ver[ver_idx][j][k] = min(extent_ver[!ver_idx][j][k - 1], extent_hor[i][j]);
                if (!extent_ver[ver_idx][j][k])
                    break;
                tmp_best = max(tmp_best, extent_ver[ver_idx][j][k] + k);
            }
        }
        final_res = max(final_res, tmp_best);
        // printf("# row %d -> %d\n", i, tmp_best);
        // for (int k = 1; k <= n + 1 - i; cout << endl, k++)
        //     for (int j = 1; j <= m; j++)
        //         printf("%d ", extent_ver[ver_idx][j][k]);
        // cout << endl;
        ver_idx = !ver_idx;
    }
    printf("%d\n", final_res * 2 - 1);
    return 0;
}