牛客暑假训练2 C.Red Walking on Grid

原题链接:C-Red Walking on Grid

题意:宽为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;
}

相关推荐

  1. 暑假训练2 C.Red Walking on Grid

    2024-07-21 16:16:01       30 阅读
  2. 2024暑期多校训练营1 I.Mirror Maze(题解)

    2024-07-21 16:16:01       32 阅读
  3. 多校暑期第一场

    2024-07-21 16:16:01       26 阅读
  4. C++知识点2

    2024-07-21 16:16:01       64 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-21 16:16:01       145 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-21 16:16:01       159 阅读
  3. 在Django里面运行非项目文件

    2024-07-21 16:16:01       133 阅读
  4. Python语言-面向对象

    2024-07-21 16:16:01       145 阅读

热门阅读

  1. Python之后端Django(六)

    2024-07-21 16:16:01       25 阅读
  2. blender和3dmax和maya和c4d比较

    2024-07-21 16:16:01       26 阅读
  3. 数据结构第33节 在不同领域的应用

    2024-07-21 16:16:01       23 阅读
  4. 【软考】UML中的关联关系

    2024-07-21 16:16:01       32 阅读
  5. firefly rk3288 ubuntu23.10 网卡名为end0 改为eth0

    2024-07-21 16:16:01       25 阅读
  6. C++狼人杀游戏(真的能运行!!!)

    2024-07-21 16:16:01       25 阅读
  7. 跨平台游戏引擎 Axmol-2.1.4 发布

    2024-07-21 16:16:01       34 阅读
  8. 使用 hutool工具实现导入导出功能。

    2024-07-21 16:16:01       35 阅读
  9. https证书申请

    2024-07-21 16:16:01       31 阅读
  10. feign 报错 Connection reset executing POST

    2024-07-21 16:16:01       28 阅读
  11. Python 热门面试题(七)

    2024-07-21 16:16:01       28 阅读
  12. 基本的DQL语句-单表查询

    2024-07-21 16:16:01       30 阅读
  13. ios CCUIFont.m

    2024-07-21 16:16:01       29 阅读
  14. 【机器学习基础】机器学习基本概念和常用算法

    2024-07-21 16:16:01       33 阅读