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

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++大富翁游戏

【问题描述】 小明很喜欢玩大富翁游戏&#xff0c;这个游戏的规则如下&#xff1a; 1、游戏地图是有 N 个格子&#xff0c;分别编号从 1 到 N。玩家一开始位于 1 号格子。 2、地图的每个格子上都有事件&#xff0c;事件有以下两种类型&#xff1a; A&#xff09;罚款 x 枚金币…...

React获取form表单值的N种方式

Ref模式&#xff08;非受控模式&#xff09; 非钩子模式 1.createRef()方式 js: userNameElcreateRef() <input type"text" name"userName" ref{this.userNameEl} /> 获取值的方式&#xff1a; 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容器&#xff0c;它实现了Java Servlet、JavaServer Pages (JSP) 和WebSocket规范。Tomcat的核心设计围绕着几个关键组件&#xff0c;它们共同构成了处理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监听事件汇总

一、监听单选按钮事件 点击资源类型单选按钮时&#xff0c;请求后台接口&#xff0c;把接口返回的内容追加到选择资源下拉框内 HTML <div class"layui-form-item"><label class"layui-form-label">资源类型&#xff1a;</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如何从提取文档中提取内容&#xff08;word、pdf、txt、excel等文件类型&#xff09;&#xff0c;实现快速检索文档内容实现。 特别说明一下&#xff0c;为什么用7.10.0版本&#xff0c;因为在项目中除了精确匹配的要求&#xff0c;也会有模糊查询&#xff08;关…...

[初学rust] 04_rust复合类型

rust复合类型 字符串 由于rust的字符串元素类型是u8(1字节),但是字符类型是unicode(4字节) 索引不能像C那样读取又由于String类型和&str类型都是utf-8编码&#xff0c;中文占3字节切片可能会导致崩溃 slice(切片) 切片就是对String类型中的一部分的引用&#xff0c;它…...

什么是Zoho CRM客户关系系统管理?

以客户为中心的商业时代&#xff0c;卓越的客户体验已成为企业持续增长与成功的关键,为了在这场激烈的市场竞争中脱颖而出&#xff0c;企业需要一套强大、灵活且智能的客户关系管理系统——Zoho CRM应运而生&#xff0c;它不仅是管理客户信息的工具箱&#xff0c;更是驱动业务增…...

青岛东软载波子公司东软载波微电子授权世强硬创代理,出货量累计超20亿颗

凭借业内独特的互联网推新模式&#xff0c;世强先进&#xff08;深圳&#xff09;科技股份有限公司&#xff08;下称“世强先进”&#xff09; 获得本土工业MCU企业——上海东软载波微电子有限公司&#xff08;下称“东软载波微电子”&#xff0c;英文&#xff1a;essemi&#…...

YOLO损失函数——SIoU和Focal Lossr损失函数解析

1. 概述 YOLO&#xff08;You Only Look Once&#xff09; 系列模型以其实时目标检测能力而闻名&#xff0c;其有效性在很大程度上归功于其专门设计的损失函数。在本文中&#xff0c;这里将深入探讨YOLO演进中不可或缺的各种YOLO损失函数&#xff0c;并重点介绍它们在PyTorch中…...

C++:编程世界的永恒之石

在编程的广袤领域中&#xff0c;C犹如一块永恒的基石&#xff0c;历经岁月的洗礼&#xff0c;依旧坚固而璀璨。它的深厚底蕴、强大功能和广泛的应用领域&#xff0c;使其成为无数程序员心中的信仰与追求。 一、C&#xff1a;历史与传承的交汇点 C的历史可追溯到上世纪80年代&…...

线上3D博物馆搭建简单吗?有何优势?有哪些应用场景?

随着科技的飞速发展&#xff0c;传统的博物馆参观方式正在经历一场前所未有的变革&#xff0c;在科技的“加持”下&#xff0c;不少博物馆凭借强大的技术、创意和美学实践&#xff0c;频频“出圈”&#xff0c;线上3D博物馆逐渐崛起&#xff0c;这不仅丰富了人们的文化体验&…...

Rust 语言的“命名空间” —— mod

在Rust中&#xff0c;虽然没有像C中的namespace这样的显式关键字&#xff0c;但是Rust通过模块&#xff08;mod&#xff09;系统提供了一种类似命名空间的功能。模块允许你将相关的代码组织在一起&#xff0c;并可以通过pub关键字来控制哪些项&#xff08;如函数、结构体、枚举…...

加速科技突破2.7G高速数据接口测试技术

随着显示面板分辨率的不断提升&#xff0c;显示驱动芯片&#xff08;DDIC&#xff09;的数据接口传输速率越来越高&#xff0c;MIPI、LVDS/mLVDS、HDMI等高速数据接口在DDIC上广泛应用。为满足高速数据接口的ATE测试需求&#xff0c;作为国内少数拥有完全自研的LCD Driver测试解…...

从0开始搭建一个react项目 第一 二 三天

从0开始搭建一个react项目 今天接到一个任务让我把原来用ext.js写的前端换成react写的&#xff0c;我好慌的&#xff0c;因为我就是一个小白&#xff0c;之前只做过简单的二次开发功能。唉&#xff0c;我只是一个领着微薄薪水的小实习生&#xff0c;为什么要有这个任务&#x…...

LSTM与GAN创新结合!模型性能起飞,准确率超98%

今天来聊一个深度学习领域非常具有创新性的研究方向&#xff1a;LSTM结合GAN。 LSTM擅长处理和记忆长期的时间依赖关系&#xff0c;而GAN可以学习复杂的数据分布并生成逼真的数据样本。通过充分结合两者的优势&#xff0c;我们可以增强模型对复杂数据的处理能力&#xff0c;提…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...