当前位置: 首页 > news >正文

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

文章目录 索引创建索引删除索引索引优点及缺点&#xff1f;避免使用索引 视图创建视图删除视图 事务事务控制命令通过事务方式对数据库进行访问优势&#xff1a; 索引 创建索引 索引&#xff08;Index&#xff09;是一种特殊查找表&#xff0c;数据库搜索引擎用来加速数据检索…...

学籍管理平台|在线学籍管理平台系统|基于Springboot+VUE的在线学籍管理平台系统设计与实现(源码+数据库+文档)

在线学籍管理平台系统 目录 基于SpringbootVUE的在线学籍管理平台系统设计与实现 一、前言 二、系统功能设计 三、系统实现 四、数据库设计 1、实体ER图 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介绍&#xff1a;✌️大…...

JDBC编程

前言&#xff1a; 你是否见过用Java连接数据库的操作&#xff0c;对没错&#xff0c;今天我们要讲的就是这个“高级”操作&#xff0c;做好准备全程高速。 API&#xff1a; 什么是API&#xff1f;我喜欢先把它的全称说一下&#xff1a;Application Programming Interface。简…...

Python : 类变量、静态方法、类方法

文章目录 前言1 类变量(Java静态变量)2 Python中的静态方法(使用 @staticmethod 装饰器声明)3 类方法(使用 @classmethod 装饰器声明)4 静态方法和类方法的区别前言 学完Java过后,对python中有了一些疑惑。Java中有static修饰的静态变量和静态方法这两个很用用的知识点…...

大厂笔试现已经禁用本地IDE怎么看

如果我说本来面试做题这种事情就是反人类你相信吗&#xff1f; 这个罪恶的源头就是 Google&#xff0c;说是为了选择高素质的计算机编程水平的人才&#xff0c;然后把面试就变成了考试&#xff0c;最大的受益者当然是印度人了。 当把一个考察过程变成标准化的考试过程&#x…...

【PostgreSQL】入门篇——如何创建、删除和管理数据库及其用户,包括权限设置和角色管理

PostgreSQL 数据库及用户管理 1. 创建数据库 1.1 使用 SQL 命令创建数据库 在 PostgreSQL 中&#xff0c;可以使用 CREATE DATABASE 命令来创建数据库。以下是基本语法&#xff1a; CREATE DATABASE database_name;示例&#xff1a; CREATE DATABASE my_database;1.2 使用…...

网络安全:保护数字时代的堡垒

网络安全&#xff1a;保护数字时代的堡垒 引言&#xff1a; 在数字化时代&#xff0c;网络安全的重要性日益凸显。它不仅关系到个人隐私保护&#xff0c;还涉及国家安全和经济发展。随着技术的发展&#xff0c;网络安全的威胁也在不断进化&#xff0c;从个人设备到企业网络&am…...

【rCore OS 开源操作系统】Rust 字符串(可变字符串String与字符串切片str)

【rCore OS 开源操作系统】Rust 语法详解: Strings 前言 这次涉及到的题目相对来说比较有深度&#xff0c;涉及到 Rust 新手们容易困惑的点。 这一次在直接开始做题之前&#xff0c;先来学习下字符串相关的知识。 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 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说&#xff0c;nums 的每个元素都恰好被某个区间范围所覆盖&#xff0c;并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中…...

NVIDIA网卡系列之ConnectX-6 DX规格信息(200G-PCIe 4.0x16-8PF1000VF-2019年发布)

背景 NVIDIA ConnectX-6是最大支持200G的产品&#xff0c;有DX LX等系列。LX一般是25G比较便宜。 核心关键点 200GbpsPCIe 4.0&#xff0c;最大lane: x16 (4.0的lane速 16GT/s * 16 256T/s&#xff0c;所以支持的是200G的网卡用PCIe4.0)QSFPPF&#xff0c;VF数量&#xff1…...

【案例】平面云

教程案例视频&#xff1a;Unity Shader Graph - 云教程 开发平台&#xff1a;Unity 2022 开发工具&#xff1a;Unity ShaderGraph   一、效果展示 二、ShaderGraph 路线图 三、案例分析 核心思路&#xff1a;使用 Noise&#xff08;噪声&#xff09;模拟云层状态   3.1 说明…...

测试用例的进阶二

1. 按开发阶段划分 1.1 测试金字塔 从上到下&#xff0c;对于测试人员代码就是要求越来越低&#xff1b; 从下到上&#xff0c;越来越靠近用户&#xff1b; 从下到上&#xff0c;定位问题的成本越来越高&#xff1b; 1.2 单元测试(Unit Testing) 单元测试是对软件组成单元进…...

zotero WebDAV同步忘记密码

https://www.jianguoyun.com/#/safety 找到应用密码...

如何在 SQL 中创建一个新的数据库?

在SQL中创建一个新的数据库&#xff0c;首先你需要有一个可以执行SQL语句的环境。 这通常意味着你已经有了一个数据库管理系统&#xff08;DBMS&#xff09;&#xff0c;如MySQL、PostgreSQL、Oracle或Microsoft SQL Server等。 不同的DBMS可能有不同的细节&#xff0c;但基本…...

《Linux从小白到高手》理论篇:Linux的进程管理详解

本篇将介绍Linux的进程管理相关知识&#xff0c;并将深入介绍Linux的进程间相互通信。 进程就是运行中的程序&#xff0c;一个运行着的程序&#xff0c;可能有多个进程。 比如Oracle DB&#xff0c;启动Oracle实例服务后&#xff0c;就会有多个进程。 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&#xff1a;全球分布式数据库-Schema对象&#xff08;20241004&#xff09;1 分区、表空间和Chunk&#xff08;块&#xff09;2 表空间组3 分片表4 分片表族5 复制表6 在所有分片上创建的非表对象总结 数据库管理-第247期 …...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

算法笔记2

1.字符串拼接最好用StringBuilder&#xff0c;不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...