「Bzoj 1057」「ZJOI2007」棋盘制作 (DP悬线法/单调栈)

发表于 | 分类于 | | + s

Bzoj 1057
题意：在一个大矩阵中找出一个黑白相间最大的正方形和最大的矩形。
DP悬线法解：
求最大正方形可以用DP，而矩形就要悬线法(正方形也可以这样求)。
预处理$l,r$数组为当前行左右最远能到达的合法格。然后每次查询看能否合并上一行的状态，处理$up$数组为往上最远能到达的合法格。转移方法和DP差不多。正方形取两个最小值的平方，长方形直接乘即可。
单调栈解：
先来考虑 Poj 2559 的做法：
将所有高度依次加入单调栈，若出现破坏单增情况，则弹出栈直到满足为止。弹出过程中顺便记录以当前弹出高度为高，累加弹出宽度为宽求答案。最后将新的宽度+高度加入单调栈。注意最后剩余情况，直接在后面加一个高度为 0 的即可。(具体看算法竞赛进阶指南)

然后本题矩形考虑行列分开处理，对每个位置的数求出列上最高可达点，然后对于每行来说就是做 Poj 2559 的事情。所以直接每行做一次。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 2000 + 5;

int n, m, a[MAXN][MAXN], up[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN];

void clean() {
    ms(l, 0), ms(r, 0);
} 
int solve() {
    clean();
    for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]), up[i][j] = 1, l[i][j] = r[i][j] = j;

    for (int i = 1; i <= n; i++) {
        l[i][0] = 1, r[i][m] = m;
        for (int j = 2; j <= m; j++) if (a[i][j] != a[i][j - 1]) l[i][j] = l[i][j - 1];
        for (int j = m - 1; j; j--) if (a[i][j] != a[i][j + 1]) r[i][j] = r[i][j + 1];    
    } 

    /*for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++) printf("i=%d j=%d l=%d\n", i, j, r[i][j]);*/

    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i++) 
    for (int j = 1; j <= m; j++) {
        if (i != 1 && a[i][j] != a[i - 1][j]) l[i][j] = std::max(l[i][j], l[i - 1][j]), r[i][j] = std::min(r[i][j], r[i - 1][j]), up[i][j] = up[i - 1][j] + 1;
        int a = r[i][j] - l[i][j] + 1, b = std::min(a, up[i][j]);
        ans1 = std::max(ans1, b * b), ans2 = std::max(ans2, a * up[i][j]);
    }
    printf("%d\n%d\n", ans1, ans2);
    return 0;
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}

单调栈 Luogu 4147 参考：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include<utility>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 1005;

    int n, m, whw[MAXN][MAXN], s[MAXN], top, w[MAXN];
    char ma[MAXN][MAXN];

    void clean() {
        ms(whw, 0);
    }
    int solve() {
        clean();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j) {
            char ch = getchar();
            while (ch != 'F' && ch != 'R') ch = getchar();
            ma[i][j] = ch;
        }
        for (int i = 1; i <= n; ++i) 
        for (int j = 1; j <= m; ++j) if (ma[i][j] != 'R') whw[i][j] = whw[i - 1][j] + 1;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            top = 0;
            for (int j = 1; j <= m + 1; ++j) {
                if (s[top] <= whw[i][j]) s[++top] = whw[i][j], w[top] = 1;
                else {
                    int tmp = 0;
                    while (top && s[top] > whw[i][j]) tmp += w[top], ans = max(ans, tmp * s[top]), --top;
                    w[++top] = tmp + 1, s[top] = whw[i][j];
                }
            }
        }
        printf("%d\n", ans * 3);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
3 3
F F R 
R F F 
F F F 
*/
------ 本文结束 ------