跳转至

CF1393D

知识点

  • 动态规划
  • 悬线法

题意简述

给定一个 \(n \times m\) 的矩阵 \(A\),求矩阵中所有的(可重叠)每个元素均相等的斜 \(45^{\circ}\) 的正方形的边长的总个数1

数据范围:\(1 \le n, m \le 2\cdot 10^3\)

一些「合法的斜正方形」和「不合法的斜正方形」的例子

合法的斜正方形:

合法的斜正方形

不合法的斜正方形:

不合法的斜正方形

解题思路

\(f(i, j)\) 表示以 \((i, j)\) 为最下方的边界,最大的合法的正方形,此边界到正方形中心的距离。

不难发现答案为 \(\textrm{ans} = \sum_{i = 1}^{n}\sum_{j = 1}^{m}f(i, j)\)

如果 \((i, j)\) 能被左上方区域拓展出来,那么一定要满足 \(A_{i, j} = A_{i - 1, j - 1} = A_{i - 1, j} = A_{i - 1, j + 1} = A_{i - 2, j}\)

递推式即为 \(f(i, j) = \min\{f(i - 1, j - 1), f(i - 1, j), f(i - 2, j)\} + 1\)

代码实现

核心部分已用高亮标出。

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
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define LL long long

namespace io {
    template <typename T> inline void read(T & _x) {
        int f = 0, ch; _x = 0;
        while(!isdigit(ch = getchar())) f |= ch == '-';
        while(isdigit(ch)) _x = _x * 10 + ch - '0', ch = getchar();
        if(f) _x = -_x;
    }
    template <typename T, typename ... Args> inline void read(T &_f, Args& ... args) {
        read(_f), read(args ...);
    }
    inline void _deal(char ch) { putchar(ch); }
    template <typename T> inline void _deal(T _x) {
        if (_x < 0) putchar('-'), _x = -_x;
        if (_x > 9) _deal(_x / 10);
        putchar(_x % 10 + '0');
    }
    inline void write() {}
    template <typename T, typename ... Args> inline void write(T _f, Args ... args) {
        _deal(_f), write(args...);
    }
}

const int N = 2e3 + 5;
const int M = 2e3 + 5;

int n, m, f[N][M], ans;
char a[N][M];

int32_t main() {
    io::read(n, m);
    for(int i = 1; i <= n; ++i)
        scanf("%s", a[i] + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j) {
            f[i][j] = 1;
            if(2 < i && 1 < j && j < m
            && a[i][j] == a[i - 1][j - 1]
            && a[i][j] == a[i - 1][j]
            && a[i][j] == a[i - 1][j + 1]
            && a[i][j] == a[i - 2][j])
                f[i][j] = std::min(f[i - 1][j - 1], std::min(f[i - 1][j + 1], f[i - 2][j])) + 1;
            ans += f[i][j];
        }
    io::write(ans);
    return 0;
}

  1. 原题链接: D. Rarity and New Dress