CCF PTA 2022年11月C++大富翁游戏
【问题描述】
小明很喜欢玩大富翁游戏,这个游戏的规则如下: 1、游戏地图是有 N 个格子,分别编号从 1 到 N。玩家一开始位于 1 号格子。 2、地图的每个格子上都有事件,事件有以下两种类型: A)罚款 x 枚金币。如果 x 为负数,则表示获得-x 枚金币; B)强制前进 y 个格子(输入数据保证,前进后不会越过 N 号格子)。 3、游戏开始时首先触发 1 号格子的事件,然后开始玩家回合。 4、玩家每回合可以选择前进 1 或 2 个格子(不可以不移动,不可以越过 N 号格子),之后触发停 留的格子的事件。 4.1、如果触发的是 A 类事件,进行罚款。若罚款后金币数小于 0,则游戏失败,否则继续下一个 回合; 4.2、如果触发的是 B 类事件,强行前进。若强行前进后所在的格子为 A 类事件,则按照 4.1 的规 则触发 A 类事件;若为 B 类事件,则当前回合不再触发 B 类事件。 5、如果玩家回合结束时,处在 N 号格子,且金币数大于等于 0,则游戏胜利。 可以看出,如果玩家一开始有足够多的金币,总是能够通过合理选择前进方案获得胜利。小明想 知道,一开始最少需要多少金币,才有可能取得游戏胜利?
【输入描述】
第一行给出正整数 N,为地图的长度。 接下来 N 行,分别描述从 1 到 N 号格子的事件:A x 或者 B y。
【输出描述】
一个整数,要取得游戏胜利,最少需要的金币数。
【输入样例】
7
A -2
A 3
B 1
A 2
A 4
A 2
A 0
【输出样例】
2
【数据规模】
100%数据满足2 ≤ 𝑁 ≤ 128,−8 ≤ 𝑥 ≤ 8,0 ≤ 𝑦 ≤ 2。
【题解】
本题关键点:动态规划,代码如下。
#include <iostream>
using namespace std;
//动态规划,由最后一个格子依次往前计算每个格子所需的最少金币
//玩家在n+1号格子,且触发完事件,面临回合选择时,最少持有map[n].cost个金币const int MAX_CELL=128;
struct cell{char type;int xy;int cost;
};
cell map[MAX_CELL];
int main(){int N=0;cin>>N;for(int n=0;n<N;n++){cin>>map[n].type>>map[n].xy;}map[N-1].cost=0;//动态规划 for(int n=N-2;n>=0;n--){int cost=0;//求cost:n+1号格子最少需要多少金币for(int d=1;d<=2 && n+d<N;d++){int ncost=0;if(map[n+d].type=='A'){ncost=map[n+d].xy+map[n+d].cost;}else{int nd = n+d+map[n+d].xy;if(map[nd].type=='A'){ncost=map[nd].xy+map[nd].cost;}else{ncost=map[nd].cost;}}if(d==1 || cost>ncost)cost=ncost;}if(cost<0)cost=0;map[n].cost=cost; }int total=0;//求total:游戏开始时最少需要多少金币if(map[0].type=='A'){total=map[0].xy+map[0].cost;}else{int nd=map[0].xy;if(map[nd].type=='A'){total=map[nd].xy+map[nd].cost;}else{total=map[nd].cost;}}if(total<0)total=0;cout<<total<<endl; return 0;
}
相关文章:
CCF PTA 2022年11月C++大富翁游戏
【问题描述】 小明很喜欢玩大富翁游戏,这个游戏的规则如下: 1、游戏地图是有 N 个格子,分别编号从 1 到 N。玩家一开始位于 1 号格子。 2、地图的每个格子上都有事件,事件有以下两种类型: A)罚款 x 枚金币…...
React获取form表单值的N种方式
Ref模式(非受控模式) 非钩子模式 1.createRef()方式 js: userNameElcreateRef() <input type"text" name"userName" ref{this.userNameEl} /> 获取值的方式: this.userNameEl.current.value2.refs(废弃) js: con…...
Apache Knox 2.0.0使用
目录 介绍 使用 gateway-site.xml users.ldif my_hdfs.xml my_yarn.xml 其它 介绍 The Apache Knox Gateway is a system that provides a single point of authentication and access for Apache Hadoop services in a cluster. The goal is to simplify Hadoop securit…...
Tomcat 内核详解 - Web服务器机制
详细介绍 Apache Tomcat 是一个开源的Web服务器和Servlet容器,它实现了Java Servlet、JavaServer Pages (JSP) 和WebSocket规范。Tomcat的核心设计围绕着几个关键组件,它们共同构成了处理HTTP请求、管理Web应用部署和执行Servlet逻辑的基础架构。 Apac…...
几个人脸库对于面部动作识别的功能比较
经粗略研究,insightface只能识别面部特征点的位置,根据这些位置不能直接推出一个人是否在睡觉。 OpenFace 是一个高级的面部行为分析工具,它能够识别和分析多种面部动作单位(Facial Action Coding System, FACS),这些动作单位是根据面部肌肉活动定义的。每个动作单位(A…...
IDEA 使用Alibaba Cloud Toolkit 实现远程 自动部署
安装插件 maven方式部署 配置服务器主机信息 配置发布到主机 单击Select 单击run 就可以将选择module的jar文件上传到服务器的指定位置了 Alibaba Cloud Toolkit 上传文件的方式部署...
蓝桥杯备战15.完全二叉树的权值
P8681 [蓝桥杯 2019 省 AB] 完全二叉树的权值 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) #include<bits/stdc.h> using namespace std; #define endl \n #define int long long const int N 2e510; int a[N]; signed main() {std::ios::sync_with_stdio(0),cin.ti…...
【前端】LayUI监听事件汇总
一、监听单选按钮事件 点击资源类型单选按钮时,请求后台接口,把接口返回的内容追加到选择资源下拉框内 HTML <div class"layui-form-item"><label class"layui-form-label">资源类型:</label><d…...
【多电压流程 Multivoltage Flow】- 5.特定工具使用建议(1.VCS NLP VC LP)
本章提供了关于使用Synopsys工具进行低功耗设计和分析的信息。它包含以下部分: • 使用VCS NLP和VC LP进行多电压验证 • 使用Design Compiler进行逻辑综合 • 使用IC Compiler进行设计规划 • 使用IC Compiler进行物理实现 • 使用IC Compiler II和Fusion Compiler进行物…...
Elasticsearch 实现word、pdf、txt、excel文档内容快速检索(保姆级教程)
本文主要讲解ES如何从提取文档中提取内容(word、pdf、txt、excel等文件类型),实现快速检索文档内容实现。 特别说明一下,为什么用7.10.0版本,因为在项目中除了精确匹配的要求,也会有模糊查询(关…...
[初学rust] 04_rust复合类型
rust复合类型 字符串 由于rust的字符串元素类型是u8(1字节),但是字符类型是unicode(4字节) 索引不能像C那样读取又由于String类型和&str类型都是utf-8编码,中文占3字节切片可能会导致崩溃 slice(切片) 切片就是对String类型中的一部分的引用,它…...
什么是Zoho CRM客户关系系统管理?
以客户为中心的商业时代,卓越的客户体验已成为企业持续增长与成功的关键,为了在这场激烈的市场竞争中脱颖而出,企业需要一套强大、灵活且智能的客户关系管理系统——Zoho CRM应运而生,它不仅是管理客户信息的工具箱,更是驱动业务增…...
青岛东软载波子公司东软载波微电子授权世强硬创代理,出货量累计超20亿颗
凭借业内独特的互联网推新模式,世强先进(深圳)科技股份有限公司(下称“世强先进”) 获得本土工业MCU企业——上海东软载波微电子有限公司(下称“东软载波微电子”,英文:essemi&#…...
YOLO损失函数——SIoU和Focal Lossr损失函数解析
1. 概述 YOLO(You Only Look Once) 系列模型以其实时目标检测能力而闻名,其有效性在很大程度上归功于其专门设计的损失函数。在本文中,这里将深入探讨YOLO演进中不可或缺的各种YOLO损失函数,并重点介绍它们在PyTorch中…...
C++:编程世界的永恒之石
在编程的广袤领域中,C犹如一块永恒的基石,历经岁月的洗礼,依旧坚固而璀璨。它的深厚底蕴、强大功能和广泛的应用领域,使其成为无数程序员心中的信仰与追求。 一、C:历史与传承的交汇点 C的历史可追溯到上世纪80年代&…...
线上3D博物馆搭建简单吗?有何优势?有哪些应用场景?
随着科技的飞速发展,传统的博物馆参观方式正在经历一场前所未有的变革,在科技的“加持”下,不少博物馆凭借强大的技术、创意和美学实践,频频“出圈”,线上3D博物馆逐渐崛起,这不仅丰富了人们的文化体验&…...
Rust 语言的“命名空间” —— mod
在Rust中,虽然没有像C中的namespace这样的显式关键字,但是Rust通过模块(mod)系统提供了一种类似命名空间的功能。模块允许你将相关的代码组织在一起,并可以通过pub关键字来控制哪些项(如函数、结构体、枚举…...
加速科技突破2.7G高速数据接口测试技术
随着显示面板分辨率的不断提升,显示驱动芯片(DDIC)的数据接口传输速率越来越高,MIPI、LVDS/mLVDS、HDMI等高速数据接口在DDIC上广泛应用。为满足高速数据接口的ATE测试需求,作为国内少数拥有完全自研的LCD Driver测试解…...
从0开始搭建一个react项目 第一 二 三天
从0开始搭建一个react项目 今天接到一个任务让我把原来用ext.js写的前端换成react写的,我好慌的,因为我就是一个小白,之前只做过简单的二次开发功能。唉,我只是一个领着微薄薪水的小实习生,为什么要有这个任务&#x…...
LSTM与GAN创新结合!模型性能起飞,准确率超98%
今天来聊一个深度学习领域非常具有创新性的研究方向:LSTM结合GAN。 LSTM擅长处理和记忆长期的时间依赖关系,而GAN可以学习复杂的数据分布并生成逼真的数据样本。通过充分结合两者的优势,我们可以增强模型对复杂数据的处理能力,提…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
