英文题干

Red is on a 2⋅n grid, with some cells being red and others being white.

Red can initially choose a red cell, and at each step, can choose a red cell above, below, to the left, or to the right. When Red leaves a cell, the cell immediately turns white.

Red wants to know the maximum number of steps she can take.

If there are no initial red cells, please output 0.

Input:

The first line contains a positive integer 𝑛 ().

The next two lines contain a 2⋅𝑛 character matrix, consisting only of 'R' and 'W' characters. 'R' represents a red cell, and 'W' represents a white cell.

Output:

An integer — the maximum number of steps Red can take.

中文题干

Red位于一个2×n的网格上，其中一些单元格是红色的，而其他单元格是白色的。

Red可以最初选择一个红色单元格，并在每一步中，可以选择上方、下方、左侧或右侧的红色单元格。当Red离开一个单元格时，该单元格立即变为白色。

Red想要知道她可以走的最大步数。如果没有初始红色单元格，请输出0。

思路

输入读取

初始化一个step数组用于记录每个红色单元格的步数，并初始化步数为1。

dp遍历

遍历每一列，根据上一列的步数情况，更新当前列的步数。

对于每一列，有三种情况：

  1. 上一列两个位置都没有红色单元格。
  2. 上一列两个位置的步数相同且不为零。
  3. 上一列两个位置的步数不同。

详细步数更新规则：

  1. 情况1：如果上一列两个位置都没有红色单元格，当前列两个位置都为红色，则步数设为2（因为可以从上一列到当前列走两步）。

  2. 情况2：如果上一列两个位置步数相同且不为零，当前列的步数根据当前列的红色格子个数可以为(上一列步数+2)或(上一列步数+1)。

  3. 情况3：根据上一列的步数不同情况，更新当前列的位置：

    [1].如果上一列第一行的步数大于第二行，则当前列第一行的步数为(上一列第一行步数+1)，第二行步数为(当前列第一行步数+1)。

    [2].如果上一列第二行的步数大于第一行，则当前列第二行的步数为(上一列第二行步数+1)，第一行步数为(当前列第二行步数+1)。

求最大步数

最后遍历 step 数组，找到最大步数值，并输出最大步数减一的结果（因为初始步数设为 1）。

AC代码

时间复杂度：O(n)，空间复杂度：O(n)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

int n;
char mtr[3][maxn];
int step[3][maxn];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= 2; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> mtr[i][j];
            if (mtr[i][j] == 'R')
                step[i][j] = 1;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (step[1][i - 1] == 0 && step[2][i - 1] == 0)
        {
            if (step[1][i] != 0 && step[2][i] != 0)
            {
                step[1][i] = 2;
                step[2][i] = 2;
            }
        }

        else if (step[1][i - 1] == step[2][i - 1] && step[1][i - 1] != 0)
        {
            if (step[1][i] != 0)
            {
                if (step[2][i] != 0)
                    step[1][i] = step[1][i - 1] + 2;
                else
                    step[1][i] = step[1][i - 1] + 1;
            }

            if (step[2][i] != 0)
            {
                if (step[1][i] != 0)
                    step[2][i] = step[1][i - 1] + 2;
                else
                    step[2][i] = step[1][i - 1] + 1;
            }
        }

        else
        {
            if (step[1][i - 1] > step[2][i - 1])
            {
                if (step[1][i] != 0)
                {
                    step[1][i] = step[1][i - 1] + 1;
                    if (step[2][i] != 0)
                        step[2][i] = step[1][i] + 1;
                }

                else if (step[2][i] != 0)
                    step[2][i] = step[2][i - 1] + 1;
            }
            else
            {
                if (step[2][i] != 0)
                {
                    step[2][i] = step[2][i - 1] + 1;
                    if (step[1][i] != 0)
                        step[1][i] = step[2][i] + 1;
                }
                else if (step[1][i] != 0)
                    step[1][i] = step[1][i - 1] + 1;
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= 2; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            ans = max(ans, step[i][j]);
        }
    }

    if (ans != 0)
        cout << ans - 1;
    else
        cout << 0;

    return 0;
}
// Inspired by LXY