BBQ

题目描述

You are a master of barbeque, and now you are trying to string dumplings with a bamboo stick.

The dumplings are placed in a $n \times m$ grid. Each grid contains exactly one dumpling. The color of each dumpling is red ("R"), green ("G") or white ("W").

You can choose three consecutive grids from left to right, or from top to bottom, and string the corresponding dumplings into a string from left to right or from top to bottom. So there will be exactly three dumplings on a string, let’s denote a string of dumpling by their colors in order.

Now, you want to make strings "RGW" as many as possible. Note that the dumplings can not be reused in multiple strings. So how many strings "RGW" can you make?

题意概述

给定一个$n \times m$的字符矩阵。每次可以从上到下或从左到右取连续三个字符构成一个字符串，每个字符只能取一次。求最多能取几个RGW。

数据范围：$1 \le n, m \le 3000$。

算法分析

只需考虑最多能取几个G。可以发现，只有在同一条与副对角线平行的直线上的G会相互影响。分别计算每一条直线，令$f_{i, 0/1/2}$表示第$i$个位置不取/从左到右取/从上到下取的情况下，前$i$个位置最多能取几个G。最后把所有直线的结果加起来得到答案。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 3005;
char mp[N][N];
int f[N][N][3];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", mp[i] + 1);
    }
    for (int k = 2; k <= n + m; ++k) {
        for (int i = 1; i < k; ++i) {
            int j = k - i;
            if (i <= n && j <= m) {
                f[i][j][0] = std::max(f[i - 1][j + 1][0], std::max(f[i - 1][j + 1][1], f[i - 1][j + 1][2]));
                if (mp[i][j - 1] == 'R' && mp[i][j] == 'G' && mp[i][j + 1] == 'W') {
                    f[i][j][1] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][1]) + 1;
                }
                if (mp[i - 1][j] == 'R' && mp[i][j] == 'G' && mp[i + 1][j] == 'W') {
                    f[i][j][2] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][2]) + 1;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        ans += std::max(f[i][1][0], std::max(f[i][1][1], f[i][1][2]));
    }
    for (int i = 1; i <= m; ++i) {
        ans += std::max(f[n][i][0], std::max(f[n][i][1], f[n][i][2]));
    }
    printf("%d\n", ans);
    return 0;
}