## 题目描述

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; }