---
title: BBQ
tags:
  - Dynamic Programming
id: "3617"
categories:
  - - OI
    - Common Skill
date: 2020-02-04 20:40:40
---

## 题目描述

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`。最后把所有直线的结果加起来得到答案。

## 代码

```cpp
#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;
}
```