题目大意： \(2 \times n\) 大小的方格矩阵，某些格子不能走，走过的格子不能走。从任意点出发，一次最多走多少次？
首先有一个贪心的思想，每次从最左走到最右，只能向上下右走，不能向左走（因为向左走一定不会让步数更多）。
动态规划，设 \(f_{i,j}\) 表示从每个连通块走到 \((i,j)\) 的最大格子数，其中 \(i \in \{1,2\}\)，则有：
\[f_{0,i}=\max
\left\{\begin{aligned}
&f_{0,i-1}\\
&f_{1,i}
\end{aligned}\right.
\]
\[f_{1,i}=\max
\left\{\begin{aligned}
&f_{1,i-1}\\
&f_{0,i}
\end{aligned}\right.
\]
注意后面那一项需要同时计算，即不能用 \(f_{1,i}\) 更新 \(f_{0,i}\) 后又用 \(f_{0,i}\) 更新 \(f_{1,i}\)。
具体见代码：
#include<cstdio>
#include<algorithm>
using namespace std;const int N=1e6+5;
int n,f[2][N],ans;
char grid[2][N];
bool g[2][N];int main()
{scanf("%d",&n);scanf("%s%s",grid[0]+1,grid[1]+1);for(int i=0;i<=1;i++)for(int j=1;j<=n;j++)g[i][j] = grid[i][j]=='R'; //1能走，0不能走for(int i=1;i<=n;i++){if(g[0][i]) f[0][i]=max(f[0][i],f[0][i-1]+1);if(g[1][i]) f[1][i]=max(f[1][i],f[1][i-1]+1);int f0i=f[0][i],f1i=f[1][i];if(g[0][i]) f[0][i]=max(f[0][i],f1i+1);if(g[1][i]) f[1][i]=max(f[1][i],f0i+1);ans=max(ans,max(f[0][i],f[1][i]));}printf("%d\n",ans ? ans-1 : 0);return 0;
}
