【计数DP】牛客小白月赛19

登录—专业IT笔试面试备考平台_牛客网

题意

思路

首先做法一定是计数 dp

然后状态设计,先设 dp[i]

然后看影响决策的因素:两边的火焰情况,那就 dp[i][0/1][0/1]表示 前 i 个,该位有无火焰,该位右边有无火焰的方案数

在状态设计的时候一定要体现该位的状态

这样设状态也可以算贡献

然后一定就是分类讨论了

#include <bits/stdc++.h>constexpr int N = 1e6 + 10;
constexpr int mod = 1e9 + 7;int dp[N][5][5];
/*前 i 个位置, 第 i 个位置是否有 *, 第 i + 1个位置是否有 * 的方案数*/ void solve() {std::string s;std::cin >> s;int n = s.size();s = " " + s;dp[0][0][0] = dp[0][0][1] = 1;for (int i = 1; i <= n; i ++) {if (s[i] == '*') {//-*dp[i][1][0] += dp[i - 1][0][1] + dp[i - 1][1][1];dp[i][1][0] %= mod;//**dp[i][1][1] += dp[i - 1][0][1] + dp[i - 1][1][1];dp[i][1][1] %= mod;}else if (s[i] == '0') {//---dp[i][0][0] += dp[i - 1][0][0];dp[i][0][0] %= mod;}else if (s[i] == '1') {//--*dp[i][0][1] += dp[i - 1][0][0];dp[i][0][1] %= mod;//*--dp[i][0][0] += dp[i - 1][1][0];dp[i][0][0] %= mod;}else if (s[i] == '2') {//*-*dp[i][0][1] += dp[i - 1][1][0];dp[i][0][1] %= mod;}else if (s[i] == '?') {for (int j = 0; j < 2; j ++) {for (int k = 0; k < 2; k ++) {//?jkdp[i][j][k] += (dp[i - 1][0][j] + dp[i - 1][1][j]) % mod;dp[i][j][k] %= mod;}}} }std::cout << (dp[n][1][0] + dp[n][0][0]) % mod << "\n";
}
signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;while(t --) {solve();} return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/224578.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

mysql原理--连接查询的成本

1.准备工作 连接查询至少是要有两个表的&#xff0c;只有一个 single_table 表是不够的&#xff0c;所以为了故事的顺利发展&#xff0c;我们直接构造一个和 single_table 表一模一样的 single_table2 表。为了简便起见&#xff0c;我们把 single_table 表称为 s1 表&#xff0…

ES8生产实践——Kibana对接Azure AD实现单点登录

基本概念介绍 什么是单点登录 单点登录&#xff08;Single Sign-On&#xff0c;SSO&#xff09;是一种身份验证和访问控制机制&#xff0c;允许用户使用一组凭据&#xff08;通常是用户名和密码&#xff09;仅需登录一次&#xff0c;即可访问多个应用程序或系统&#xff0c;而…

结构体的对齐规则

1.引入 我们在掌握了结构体的基本使⽤后。 现在我们深⼊讨论⼀个问题&#xff1a;计算结构体的大小。 这也是⼀个特别热门的考点&#xff1a; 结构体内存对齐。 2.具体分析 ⾸先我们得掌握结构体的对⻬规则&#xff1a; 1. 结构体的第⼀个成员对⻬到和结构体变量起始位置偏移量…

一站式指南:第 377 场力扣周赛的终极题解

比赛详情 比赛地址 题目一很简单题目二主要是题目长了点&#xff0c;其实解法很常规(比赛后才意识到)题目三套用Dijkstra算法题目四没时间解答水平还有待提升(其实就是需要灵活组合运用已知的算法&#xff0c;有点类似大模型的Agent) 题解和思路 第一题&#xff1a;最小数字…

CentOS进入单用户模式

一、重启 二、出现内核选项 按“e” 三、编辑这一行 输入 rw init/sysroot/bin/sh 四、进入单用户模式 ctrlx 进入 五、切换目录 chroot /sysroot 六、然后你就操作你的系统了。 修改密码等等

【知识点随笔分享 | 第九篇】常见的限流算法

目录 前言&#xff1a; 1.固定窗口限流&#xff1a; 缺点&#xff1a; 2.滑动窗口限流&#xff1a; 优点&#xff1a; 滴桶限流&#xff1a; 缺点&#xff1a; 令牌桶限流&#xff1a; 优点&#xff1a; 总结: 前言&#xff1a; 当今互联网时代&#xff0c;随着网络…

IP编址,IP地址介绍与子网划分方法

网络层位于数据链路层与传输层之间。网络层中包含了许多协议&#xff0c;其中最为重要的协议就是IP协议。网络层提供了IP路由功能。理解IP路由除了要熟悉IP协议的工作机制之外&#xff0c;还必须理解IP编址以及如何合理地使用IP地址来设计网络。 上层协议类型 以太网帧中的Typ…

数据通信网络基础华为ICT网络赛道

目录 前言&#xff1a; 1.网络与通信 2.网络类型与网络拓扑 3.网络工程与网络工程师 前言&#xff1a; 数据通信网络基础是通信领域的基本概念&#xff0c;涉及数据传输、路由交换、网络安全等方面的知识。华为ICT网络赛道则是华为公司提出的一种技术路径&#xff0c;旨在通…

主机安全技术措施

目录 身份鉴别 进阶 访问控制 进阶 安全审计 进阶 ​编辑 剩余信息保护 入侵防范 进阶 恶意代码防范 资源控制 身份鉴别 进阶 访问控制 进阶 安全审计 进阶 剩余信息保护 入侵防范 进阶 恶意代码防范 资源控制 ~over~

Git 分布式版本控制系统(序章1)

第一章 Git 分布式版本控制系统 为什么学Git? 某些企业面试需要掌握Git&#xff0c;同时&#xff0c;也方便管理自己的Qt项目。 一、Git 客户端下载&#xff08;Windows&#xff09; 下载地址 https://gitee.com/all-about-git#git-%E5%A4%A7%E5%85%A8 二、Git 的特点 分支…

java的XWPFDocument3.17版本学习

maven依赖 <dependency><groupId>org.apache.poi</groupId><artifactId>poi-ooxml</artifactId><version>3.17</version> </dependency> 测试类&#xff1a; import org.apache.poi.openxml4j.exceptions.InvalidFormatExcep…

【MybatisPlus快速入门】(3)SpringBoot整合MybatisPlus 之 Lombok插件安装及MybatisPlus分页代码示例

目录 1.Lombok1.1 步骤1:添加lombok依赖 2.2 步骤2:安装Lombok的插件1.3 步骤3:模型类上添加注解2 分页功能2.1 步骤1:调用方法传入参数获取返回值2.2步骤2:设置分页拦截器2.3 步骤3:运行测试程序 之前我们已学习MyBatisPlus在代码示例与MyBatisPlus的简介&#xff0c;在这一节…

Web Components入门不完全指北

目前流行的各类前端框架&#xff0c;不管是react, angular还是vue&#xff0c;都有一个共同点&#xff0c;那就是支持组件化开发&#xff0c;但事实上随着浏览器的发展&#xff0c;现在浏览器也原生支持组件式开发&#xff0c;本文将通过介绍Web Components 的三个主要概念&…

vue场景 无分页列表条件过滤,子组件多选来自父组件的列表

日常开发中&#xff0c;经常会遇到下面场景&#xff1a; 页面加载一个无分页列表&#xff0c;同时工具栏设置多个条件可对列表过滤的场景(典型的就是关键字模糊查询)父组件传给子组件列表&#xff0c;子组件中需要多选列表多选&#xff0c;选择结果返回父组件 1 无分页列表过…

电子电器架构刷写方案——General Flash Bootloader

电子电器架构刷写方案——General Flash Bootloader 我是穿拖鞋的汉子&#xff0c;魔都中坚持长期主义的汽车电子工程师。 注&#xff1a;文章1万字左右&#xff0c;深度思考者入&#xff01;&#xff01;&#xff01; 老规矩&#xff0c;分享一段喜欢的文字&#xff0c;避免…

CentOS 7 Tomcat服务的安装

前提 安装ava https://blog.csdn.net/qq_36940806/article/details/134945175?spm1001.2014.3001.5501 1. 下载 wget https://mirrors.tuna.tsinghua.edu.cn/apache/tomcat/tomcat-9/v9.0.84/bin/apache-tomcat-9.0.84.tar.gzps: 可选择自己需要的版本下载安装https://mirr…

mysql原理--基于成本的优化

1.什么是成本 我们之前老说 MySQL 执行一个查询可以有不同的执行方案&#xff0c;它会选择其中成本最低&#xff0c;或者说代价最低的那种方案去真正的执行查询。不过我们之前对 成本 的描述是非常模糊的&#xff0c;其实在 MySQL 中一条查询语句的执行成本是由下边这两个方面组…

Kali Linux—借助 SET+MSF 进行网络钓鱼、生成木马、获主机shell、权限提升、远程监控、钓鱼邮件等完整渗透测试(一)

社会工程学—世界头号黑客凯文米特尼克在《欺骗的艺术》中曾提到&#xff0c;这是一种通过对受害者心理弱点、本能反应、好奇心、信任、贪婪等心理陷阱进行诸如欺骗、伤害等危害手段。 SET最常用的攻击方法有&#xff1a;用恶意附件对目标进行 E-mail 钓鱼攻击、Java Applet攻…

Unity之DOTweenPath轨迹移动

Unity之DOTweenPath轨迹移动 一、介绍 DOTweenPath二、操作说明1、Scene View Commands2、INfo3、Tween Options4、Path Tween Options5、Path Editor Options&#xff1a;轨迹编辑参数&#xff0c;就不介绍了6、ResetPath&#xff1a;重置轨迹7、Events&#xff1a;8、WayPoin…

Liteos移植_STM32_HAL库

0 开发环境 STM32CubeMX(HAL库)keil 5正点原子探索者STM32F4ZET6LiteOS-develop分支 1 STM32CubeMX创建工程 如果有自己的工程&#xff0c;直接从LiteOS源码获取开始 关于STM32CubeMX的安装&#xff0c;看我另一篇博客STM32CubeMX安装 工程配置 创建新工程 选择芯片【STM32F…