悬线Dp

Posted on Edited on In Word count in article: 357 Reading time ≈ 1 mins.
悬线Dp

[ZJOI2007]棋盘制作

这比较模板, 算是裸的悬线\(dp\)

看见\(N,M\leqslant2000\), 对了, 那就是了

时间复杂度\(O(NM)\)妥妥的

那么悬线法就是维护以这个点为某个边界条件, 维护其他边界范围

一般常用的是将这个点作为矩形的下底边, 用\(left\)维护最左边的范围, \(right\)维护最右边的范围, \(up\)维护上边界

所以这个点所在的矩阵大小就是\((right-left+1)*up\)

如果要求什么正方形之类的, 对边特殊处理一下即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 2005;
int N, M, Map[Maxn][Maxn];
int Left[Maxn][Maxn], Right[Maxn][Maxn], Up[Maxn][Maxn];
int AnsS, AnsQ;

int main()
{
    scanf ("%d %d", &N, &M);
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
            scanf ("%d", Map[i] + j), Left[i][j] = Right[i][j] = j, Up[i][j] = 1;
    
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 2; j <= M; ++j) if (Map[i][j] ^ Map[i][j - 1]) Left[i][j] = Left[i][j - 1];
        for (int j = M - 1; j; --j) if (Map[i][j + 1] ^ Map[i][j]) Right[i][j] = Right[i][j + 1];
    }

    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j)
        {
            if (i > 1 && Map[i][j] ^ Map[i - 1][j])
            {
                Left[i][j] = max(Left[i - 1][j], Left[i][j]);
                Right[i][j] = min(Right[i - 1][j], Right[i][j]);
                Up[i][j] = Up[i - 1][j] + 1;
            }
            int Len = Right[i][j] - Left[i][j] + 1;
            AnsS = max(AnsS, min(Len, Up[i][j]));
            AnsQ = max(AnsQ, Len * Up[i][j]);
        }

    printf ("%d\n%d\n", AnsS * AnsS, AnsQ);
    system ("pause");
}