D. Skipping 【 Codeforces Round 980 (Div. 2)】
D. Skipping

思路:
注意到最佳策略是先往右跳转到某处,然后按顺序从右往左把没有遇到过的题目全部提交。
将从 i i i跳转到 b [ i ] b[i] b[i]视为通过边权(代价)为 a [ i ] a[i] a[i]的路径,而向左的路径边权都是 0 0 0;目的是找到到从出发点到每个点 i i i的最短路径(最小代价) d [ i ] d[i] d[i],用Dijkstra跑一遍即可。
得分即为前缀和 p r e [ i ] pre[i] pre[i]-代价 d [ i ] d[i] d[i],将 i i i从 1 1 1遍历到 n n n,取 m a x max max即为最终答案。
代码:
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;void solve() {int n;cin >> n;int a[n + 1];for (int i = 1; i <= n; i++) {cin >> a[i];}vector<vector<pii>> lj(n + 1);for (int i = 1; i <= n; i++) {int b;cin >> b;lj[i].push_back({a[i], b});if (i != 1) lj[i].push_back({0, i - 1});}vector<bool> vis(n + 1, false);vector<int> d(n + 1, 1e15);priority_queue<pii, vector<pii>, greater<pii>> pq;pq.push({0, 1});d[1] = 0;while (!pq.empty()) {pii top = pq.top();pq.pop();int td = top.first;int tg = top.second;if (vis[tg])continue;vis[tg] = true;for (pii e : lj[tg]) {int ng = e.second;int nd = e.first;if (d[ng] > td + nd) {d[ng] = td + nd;pq.push({td + nd, ng});}}}int sum = 0, ans = 0;for (int i = 1; i <= n; i++) {sum += a[i];ans = max(ans, sum - d[i]);}cout << ans << endl;
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);int T = 1;cin >> T;while (T--) {solve();}return 0;
}
相关文章:
D. Skipping 【 Codeforces Round 980 (Div. 2)】
D. Skipping 思路: 注意到最佳策略是先往右跳转到某处,然后按顺序从右往左把没有遇到过的题目全部提交。 将从 i i i跳转到 b [ i ] b[i] b[i]视为通过边权(代价)为 a [ i ] a[i] a[i]的路径,而向左的路径边权都是 0 0 0;目的是找到到从出发…...
【golang】学习文档整理
Binding | Echo 传值时注意零值和传空的区别 需要validate require 和 设置指针配合使用 保证不同值的返回不同 不能客户端传0值被判断为空 测试时要空值零值去测试字段是否正确返回 返回错误是否符合预期...
动态规划-子序列问题——1218.最长定差子序列
1.题目解析 题目来源:1218.最长定差子序列——力扣 测试用例 2.算法原理 1.状态表示 本题可以看作是寻找一个等差序列,并且公差给出,这里并不是普通的使用一个dp表,而是将arr与dp表同时存储于一个哈希表,arr[i]映射dp…...
双子塔楼宇可视化系统:提升建筑管理与运营效率
利用图扑可视化技术对双子塔楼宇的各项功能进行实时监控和管理。通过数据分析优化资源配置,提高能源效率,增强楼宇安全性,实现智能化运营。...
32位的ARMlinux的4字节变量原子访问问题
在32位的ARM Linux内核中,4字节整型变量通常被认为是原子操作。 这主要是因为: 对齐要求:在ARM架构中,4字节整型变量通常是按4字节对齐存储的,这样可以确保在读取和写入时,CPU能够以单个指令完成操作。 …...
用哪种建站程序做谷歌SEO更容易?
做网站很容易,但做一个能带来流量和订单的网站就没那么简单了。尤其是在谷歌SEO优化方面,不同的建站程序对SEO的支持程度也不同。在这方面,WordPress和Shopify无疑是最佳选择。 WordPress作为一个内容管理系统(CMS)&am…...
IPsec简单介绍
VPN相关介绍 VPN:虚拟私有网络 例如:像这种不加密的 PPTPL2TP ------- 一般用在windows server 服务端(但是大多数企业不用这个) 假如总公司内部的PC1要去访问分公司内部的PC2(一般用在公司服务器有内网的服务&#…...
颠覆级AI:10秒生成超清视频
颠覆级AI:10秒生成超清视频 Pyramid-Flow 是一款开源 AI 视频生成神器💻,只需文字或图片即可极速生成高清视频🎥!高效、高清、资源需求低,适合创作广告、教学视频等多种用途🚀,快来…...
《西安科技大学学报》
《西安科技大学学报》主要刊载安全科学与工程、矿业工程、建筑与土木工程、地质与环境工程、测绘工程、材料科学与工程、化学与化工、机械工程、电气工程及自动化、通信与信息工程、计算机科学与工程、矿业经济管理等专业领域内具有创新性的学术论文和科研成果。 来稿必须符合以…...
redis详细教程(2.List教程)
List是一种可以存储多个有序字符串的数据类型,其中的元素按照顺序排列(可以重复出现),可以通过数字索引来访问列表中的元素,索引可以从左到右或者从右到左。 Redis 列表可以通过两种方式实现:压缩列表&…...
电子电气架构 --- 电气系统工程
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...
15-4连续子串和的整除问题
问题描述 小M是一个五年级的小学生,今天他学习了整除的知识,想通过一些练习来巩固自己的理解。他写下了一个长度为 n 的正整数序列 a_0, a_1, ..., a_{n-1},然后想知道有多少个连续子序列的和能够被一个给定的正整数 b 整除。你能帮小M解决这…...
Spring源码:Bean创建、Bean获取
Bean是怎么被创建,如何获取Bean,基于Spring 5.3.24版本,Spring Boot 可用 2.7.6 结论: 创建:非懒加载的单实例bean在容器创建的时候创建,通过beanFactory的doGetBean方法,利用反射进行创建&…...
MetaArena推出《Final Glory》:引领Web3游戏技术新风向
随着区块链技术的日益成熟,Web3游戏成为了游戏产业探索的新方向,将去中心化经济与虚拟世界结合在一起,形成了一个全新的生态体系。然而,尽管Web3游戏展示了令人兴奋的可能性,但其背后的技术障碍依旧严峻,特…...
玩转Shodan:深度挖掘特定漏洞与脆弱资产的实战技巧
内容预览 ≧∀≦ゞ Shodan进阶使用之发现并解锁隐藏的脆弱资产声明导语VNC未授权访问查询被黑的网站查询思科未授权设备查询MongoDB未授权访问搜索后台管理页面结语 Shodan进阶使用之发现并解锁隐藏的脆弱资产 声明 笔记内容参考了B站UP主泷羽sec的学习视频,如有侵…...
Java程序设计:spring boot(8)——API ⽂档构建⼯具 - Swagger2
目录 1 环境整合配置 2 Swagger2 常⽤注解说明 2.1 Api 2.2 ApiOperation 2.3 ApiImplicitParams 2.4 ApiResponses 2.5 ApiModel 3 用户模块注解配置 3.1 Controller 使用注解 3.2 JavaBean 使用注解 4 Swagger2 接⼝⽂档访问 由于 Spring Boot 能够快速开发、便捷…...
【Python】if选择判断结构详解:逻辑分支与条件判断
目录 🍔 if选择判断结构作用 1.1 if选择判断结构的基本语法 1.2 if选择结构案例 1.3 if...else...结构 1.4 if...elif...else多条件判断结构 1.5 if嵌套结构 🍔 综合案例:石头剪刀布 2.1 需求分析 2.2 代码实现 2.3 随机出拳 &…...
邮件系统SSL加密传输,保护你的电子邮件免受网络威胁
在互联网的浪潮中,企业数字化转型的步伐不断加快。企业邮箱作为数字化应用的重要组成部分,已成为员工沟通、协同工作和企业管理的关键工具。但是在公共网络安全性普遍较弱的背景下,黑客容易侵入企业网络,监控流量,截获…...
Redis_写时复制(cow)
Redis会根据配置,每隔一段时间中对Redis服务中当下的数据集进行快照。配置自动生成rdb文件,后台使用的是bgsave方式。 save 60 1000 //关闭RDB只需要将所有的save保存策略注释掉即可Redis借助操作系统提供的写时复制技术(Copy-On-Write, COW…...
【mysql进阶】4-5. InnoDB 内存结构
InnoDB 内存结构 1 InnoDB存储引擎中内存结构的主要组成部分有哪些? 🔍 分析过程 从官⽹给出的InnoDB架构图中可以找到答案 InnoDB存储引擎架构链接:https://dev.mysql.com/doc/refman/8.0/en/innodb-architecture.html ✅ 解答问题 InnoD…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
