题意:宽为2,长为n的方格,每个格子上有一种颜色,一共有二种颜色,分别是红色和白色,开始的时候选择一个红色的格子,然后每一步都可以选择上下左右的方向进行行走,问最多可以走多少步?
思路:对每一列进行考虑,从后往前,如果后一位是红色,当前位也是红色,那么当前的位置的答案就是后一位的答案加一,但是这可能并不是当前位最大的情况,如果当前位的上下位置是红色,那么就需要比较一下从上下转移过来,或者从后面转移过来的大小。
//冷静,冷静,冷静
//调不出来就重构
#pragma GCC optimize(2)
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=998244353;
char mp[3][N];
ll f[3][N],n;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=2;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
}
}
ll sm=0,xm=0;
for(int j=n;j;j--)
{
for(int i=1;i<=2;i++)
{
if(mp[i][j]=='R'&&mp[i][j+1]=='R')f[i][j]=f[i][j+1]+1;//从后一位走过来的答案
}
sm=f[1][j],xm=f[2][j];
if(mp[1][j]=='R'&&mp[2][j]=='R')//如果都是红色,那么还有一种走的方法,并且因为会多走一步,还要加上1
{
f[1][j]=max(sm,xm+1);
f[2][j]=max(sm+1,xm);
}
}
ll max1=0;
for(int i=1;i<=2;i++)
{
for(int j=1;j<=n;j++)
{
max1=max(max1,f[i][j]);
}
}
cout<<max1<<endl;
return 0;
}