题解

本题使用斜线DP求解二维网格字符串匹配问题。

算法思路：

1. 问题分析：

   • 在 $n \times m$ 的网格中，每个格子有颜色：R（红）、G（绿）、W（白）
   • 需要找到最多的不相交的"RGW"序列（可以是竖直或水平方向）
   • 统计所有可能的三色序列数量

2. 斜线DP：

   • 按斜线方向遍历网格：$x = i + j$（常数）
   • 对于每条斜线，从左上到右下处理所有格子
   • 状态 dp[i][d]：
     • $i$：在斜线上的行号
     • $d \in \{0, 1\}$：表示方向（0=竖直，1=水平）
   • 表示以位置 $(i, x-i)$ 为起点，方向 $d$ 的最大序列数

3. 标记可行位置：

   • vis[i][0] = true：位置 $(i, j)$ 可以作为竖直"RGW"的起点
   • vis[i][1] = true：位置 $(i, j)$ 可以作为水平"RGW"的起点
   • 检查 $(i, j), (i+1, j), (i+2, j)$ 或 $(i, j), (i, j+1), (i, j+2)$ 是否为"RGW"

4. 转移方程：

   • 水平方向（$d = 1$）：
     • $dp[i][1] = \max(dp[i-1][1], dp[i-2][1], mx[i-3]) + 1$
     • 可以从上方1、2、3行转移（避免冲突）
   • 竖直方向（$d = 0$）：
     • $dp[i][0] = mx[i-1] + 1$
     • 只能从上一行的最大值转移
   • mx[i]：前 $i$ 行的最大DP值

5. 答案累加：

   • 对每条斜线，计算该斜线上的最大序列数
   • 累加所有斜线的贡献（去掉负值）

时间复杂度：$O(n \times m \times (n + m))$

这是一道需要理解斜线遍历和DP状态设计的问题。

#include <cstdio>
#include <cstring>
using namespace std;
template <typename T>
T read() {T x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();} while (c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();} return x * f;}
template <typename T>
void write(T x) {if (x < 0) {putchar('-'); x = -x;} if (x > 9) write(x / 10); putchar('0' + x % 10);}
template <typename T>
void writeln(T x) {write(x); putchar('\n');}
template <typename T>
void write(T x, char c) {write(x); putchar(c);}
template <typename T>
T min_(T x, T y) {return x < y ? x : y;}
template <typename T>
T max_(T x, T y) {return x < y ? y : x;}
#define N 3005
int n, m, mp[N][N];
int dp[N][2], mx[N];
bool vis[N][2];
int main() {
	n = read<int>(); m = read<int>();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char op = getchar();
			while (op != 'R' && op != 'G' && op != 'W') op = getchar();
			mp[i][j] = (op == 'R' ? 0 : (op == 'G' ? 1 : 2));
		}
	}
	int ans = 0;
	for (int x = 2; x <= n + m - 2; x++) {
		memset(vis, 0, sizeof(vis));
		memset(dp, 0xc0, sizeof(dp));
		memset(mx, 0xc0, sizeof(mx));
		for (int i = 1; i <= x && i <= n; i++) {
			int j = x - i;
			if (j < 1 || j > m) continue;
			if (i <= n - 2 && mp[i][j] == 0 && mp[i + 1][j] == 1 && mp[i + 2][j] == 2) {
				vis[i][0] = true; dp[i][0] = 1;
//				printf("%d %d %d\n", i, j, 0);
			}
			if (j <= m - 2 && mp[i][j] == 0 && mp[i][j + 1] == 1 && mp[i][j + 2] == 2) {
				vis[i][1] = true; dp[i][1] = 1;
//				printf("%d %d %d\n", i, j, 1);
			}
		}
		int ans_ = 0;
		for (int i = 1; i <= x && i <= n; i++) {
			int j = x - i;
			if (j < 1 || j > m) continue;
			if (vis[i][1]) {
				if (i >= 2) dp[i][1] = max_(dp[i][1], dp[i - 1][1] + 1);
				if (i >= 3) dp[i][1] = max_(dp[i][1], dp[i - 2][1] + 1);
				if (i >= 4) dp[i][1] = max_(dp[i][1], mx[i - 3] + 1);
			}
			if (vis[i][0]) {
				dp[i][0] = max_(dp[i][0], mx[i - 1] + 1);
			}
//			printf("dp[%d][%d][%d] = %d\n", i, j, 0, dp[i][0]);
//			printf("dp[%d][%d][%d] = %d\n", i, j, 1, dp[i][1]);
			mx[i] = max_(mx[i - 1], max_(dp[i][0], dp[i][1]));
			ans_ = max_(ans_, mx[i]);
		}
//		putchar('\n');
		ans += max_(0, ans_);
	}
	writeln(ans);
	return 0;
}