Codeforces Beta Round 14 (Div. 2) E. Camels (DP)
题目
Bob likes to draw camels: with a single hump, two humps, three humps, etc. He draws a camel by connecting points on a coordinate plane. Now he’s drawing camels with t humps, representing them as polylines in the plane. Each polyline consists of n vertices with coordinates (x1, y1), (x2, y2), …, (xn, yn). The first vertex has a coordinate x1 = 1, the second — x2 = 2, etc. Coordinates yi might be any, but should satisfy the following conditions:
- there should be t humps precisely, i.e. such indexes j
(2 ≤ j ≤ n - 1), so that yj - 1 < yj > yj + 1, - there should be precisely t - 1 such indexes j (2 ≤ j ≤ n - 1), so
that yj - 1 > yj < yj + 1, - no segment of a polyline should be parallel to the Ox-axis,
- all yi are integers between 1 and 4.
For a series of his drawings of camels with t humps Bob wants to buy a notebook, but he doesn’t know how many pages he will need. Output the amount of different polylines that can be drawn to represent camels with t humps for a given number n.
Input
The first line contains a pair of integers n and t (3 ≤ n ≤ 20, 1 ≤ t ≤ 10).
Output
Output the required amount of camels with t humps.
Examples
input
6 1
output
6
题解
这道题的状态表示很难想,反正我是看题解的;
首先根据题目中给到的两个未知量 n, t,我们不难想到状态表示中一定是要包含 n 和 t,我们可以猜测状态方程为:
f[i][j] 表示前i个点中,包含j个驼峰的合法的方案数;
但是如何实现状态转移呢?
我们发现只用两维去表示状态无法写出转移方程,因为我们无法知道驼峰的高度,所谓的合法方案无法只被两维状态表示出来,那么我们就要引进新的状态:
用 a, b 表示上一个和上上个点的高度(y值)
因为只有知道了相邻的两个点的高度才能实现状态转移。
同时,我们不光要知道驼峰 j 的个数,还得知道驼谷 k 的个数,这样才能知道哪些方案是合法的,哪些不是。
所以最后的状态表示需要五维。
f[i][j][k][a][b] 表示填前i个y, j个波峰, k个波谷, 第i-1个y是a, 第i个y是b
知道了状态表示,状态转移就很容易写出了,直接写六重循环,分别枚举i,j,k,a,b,c(第i+1个点的y值),看满足驼峰还是满足驼谷,分别加一即可,如果状态不合法,直接延续之前的状态。
代码
#include<iostream>
#include<algorithm>
#include<cstring>using namespace std;typedef long long LL;const int N = 50;int n, t;
int f[22][22][22][5][5];int main()
{cin >> n >> t;for (int i = 1; i <= 4; i++)for (int j = 1; j <= 4; j++)if (i != j) f[2][0][0][i][j] = 1;for (int i = 2; i < n; i++)for (int j = 0; j <= t; j ++)for (int k = 0; k <= t - 1; k++)for (int a = 1; a <= 4; a++)for (int b = 1; b <= 4; b++){if(a != b)for (int c = 1; c <= 4; c++){if (b != c){if (a > b && b < c) f[i + 1][j][k + 1][b][c] += f[i][j][k][a][b]; // 这就是波谷else if (a < b && b > c) f[i + 1][j + 1][k][b][c] += f[i][j][k][a][b];else f[i + 1][j][k][b][c] += f[i][j][k][a][b];}}}LL ans = 0;for (int i = 1; i <= 4; i++)for (int j = 1; j <= 4; j++)ans += f[n][t][t - 1][i][j];cout << ans << endl;return 0;
}
相关文章:
Codeforces Beta Round 14 (Div. 2) E. Camels (DP)
题目 Bob likes to draw camels: with a single hump, two humps, three humps, etc. He draws a camel by connecting points on a coordinate plane. Now he’s drawing camels with t humps, representing them as polylines in the plane. Each polyline consists of n ve…...
CSID-GAN:基于生成对抗网络的定制风格室内平面设计框架论文阅读
CSID-GAN: A Customized Style Interior Floor Plan Design Framework Based on Generative Adversarial Network 摘要前言II. CSID-GAN METHODA. Overall FrameworkB. Algorithm and Loss Function III. DATASETS AND EVALUATION METRICSA. DatasetsB. Evaluation Metrics IV.…...
02SQLite
文章目录 索引创建索引删除索引索引优点及缺点?避免使用索引 视图创建视图删除视图 事务事务控制命令通过事务方式对数据库进行访问优势: 索引 创建索引 索引(Index)是一种特殊查找表,数据库搜索引擎用来加速数据检索…...
学籍管理平台|在线学籍管理平台系统|基于Springboot+VUE的在线学籍管理平台系统设计与实现(源码+数据库+文档)
在线学籍管理平台系统 目录 基于SpringbootVUE的在线学籍管理平台系统设计与实现 一、前言 二、系统功能设计 三、系统实现 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取: 博主介绍:✌️大…...
JDBC编程
前言: 你是否见过用Java连接数据库的操作,对没错,今天我们要讲的就是这个“高级”操作,做好准备全程高速。 API: 什么是API?我喜欢先把它的全称说一下:Application Programming Interface。简…...
Python : 类变量、静态方法、类方法
文章目录 前言1 类变量(Java静态变量)2 Python中的静态方法(使用 @staticmethod 装饰器声明)3 类方法(使用 @classmethod 装饰器声明)4 静态方法和类方法的区别前言 学完Java过后,对python中有了一些疑惑。Java中有static修饰的静态变量和静态方法这两个很用用的知识点…...
大厂笔试现已经禁用本地IDE怎么看
如果我说本来面试做题这种事情就是反人类你相信吗? 这个罪恶的源头就是 Google,说是为了选择高素质的计算机编程水平的人才,然后把面试就变成了考试,最大的受益者当然是印度人了。 当把一个考察过程变成标准化的考试过程&#x…...
【PostgreSQL】入门篇——如何创建、删除和管理数据库及其用户,包括权限设置和角色管理
PostgreSQL 数据库及用户管理 1. 创建数据库 1.1 使用 SQL 命令创建数据库 在 PostgreSQL 中,可以使用 CREATE DATABASE 命令来创建数据库。以下是基本语法: CREATE DATABASE database_name;示例: CREATE DATABASE my_database;1.2 使用…...
网络安全:保护数字时代的堡垒
网络安全:保护数字时代的堡垒 引言: 在数字化时代,网络安全的重要性日益凸显。它不仅关系到个人隐私保护,还涉及国家安全和经济发展。随着技术的发展,网络安全的威胁也在不断进化,从个人设备到企业网络&am…...
【rCore OS 开源操作系统】Rust 字符串(可变字符串String与字符串切片str)
【rCore OS 开源操作系统】Rust 语法详解: Strings 前言 这次涉及到的题目相对来说比较有深度,涉及到 Rust 新手们容易困惑的点。 这一次在直接开始做题之前,先来学习下字符串相关的知识。 Rust 的字符串 Rust中“字符串”这个概念涉及多种类型&…...
远程过程调用RPC知识科普
文章目录 什么是RPCRPC的基本原理RPC的应用场景RPC的优势常见的RPC框架 常见的RPC协议1. gRPC2. Apache Thrift3. Dubbo4. JSON-RPC5. XML-RPC6. SOAP springboot环境下常用的RPC框架使用1. Apache Dubbo2. Apache Thrift3. gRPC4. Spring Cloud OpenFeign 什么是RPC RPC&…...
Java - LeetCode面试经典150题 - 区间 (三)
区间 228. 汇总区间 题目 给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中…...
NVIDIA网卡系列之ConnectX-6 DX规格信息(200G-PCIe 4.0x16-8PF1000VF-2019年发布)
背景 NVIDIA ConnectX-6是最大支持200G的产品,有DX LX等系列。LX一般是25G比较便宜。 核心关键点 200GbpsPCIe 4.0,最大lane: x16 (4.0的lane速 16GT/s * 16 256T/s,所以支持的是200G的网卡用PCIe4.0)QSFPPF,VF数量࿱…...
【案例】平面云
教程案例视频:Unity Shader Graph - 云教程 开发平台:Unity 2022 开发工具:Unity ShaderGraph 一、效果展示 二、ShaderGraph 路线图 三、案例分析 核心思路:使用 Noise(噪声)模拟云层状态 3.1 说明…...
测试用例的进阶二
1. 按开发阶段划分 1.1 测试金字塔 从上到下,对于测试人员代码就是要求越来越低; 从下到上,越来越靠近用户; 从下到上,定位问题的成本越来越高; 1.2 单元测试(Unit Testing) 单元测试是对软件组成单元进…...
zotero WebDAV同步忘记密码
https://www.jianguoyun.com/#/safety 找到应用密码...
如何在 SQL 中创建一个新的数据库?
在SQL中创建一个新的数据库,首先你需要有一个可以执行SQL语句的环境。 这通常意味着你已经有了一个数据库管理系统(DBMS),如MySQL、PostgreSQL、Oracle或Microsoft SQL Server等。 不同的DBMS可能有不同的细节,但基本…...
《Linux从小白到高手》理论篇:Linux的进程管理详解
本篇将介绍Linux的进程管理相关知识,并将深入介绍Linux的进程间相互通信。 进程就是运行中的程序,一个运行着的程序,可能有多个进程。 比如Oracle DB,启动Oracle实例服务后,就会有多个进程。 Linux进程分类 在 Linux…...
【Qt】控件概述(3)—— 显示类控件
显示类控件 1. QLabel——标签1.1 setPixmap设置图片1.2 setAlignment设置文本对齐方式1.3 setWordWrap设置自动换行1.4 setIndent设置缩进1.5 setMargin设置边距1.6 body 2. QLCDNumber2.1 使用QTimer实现一个倒计时效果2.2 使用循环的方式实现倒计时 3. QProgressBar——进度…...
数据库管理-第247期 23ai:全球分布式数据库-Schema对象(20241004)
数据库管理247期 2024-10-04 数据库管理-第247期 23ai:全球分布式数据库-Schema对象(20241004)1 分区、表空间和Chunk(块)2 表空间组3 分片表4 分片表族5 复制表6 在所有分片上创建的非表对象总结 数据库管理-第247期 …...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...
