当前位置: 首页 > 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;提…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

【HarmonyOS 5】鸿蒙中Stage模型与FA模型详解

一、前言 在HarmonyOS 5的应用开发模型中&#xff0c;featureAbility是旧版FA模型&#xff08;Feature Ability&#xff09;的用法&#xff0c;Stage模型已采用全新的应用架构&#xff0c;推荐使用组件化的上下文获取方式&#xff0c;而非依赖featureAbility。 FA大概是API7之…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...