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

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 思路: 注意到最佳策略是先往右跳转到某处&#xff0c;然后按顺序从右往左把没有遇到过的题目全部提交。 将从 i i i跳转到 b [ i ] b[i] b[i]视为通过边权(代价)为 a [ i ] a[i] a[i]的路径&#xff0c;而向左的路径边权都是 0 0 0&#xff1b;目的是找到到从出发…...

【golang】学习文档整理

Binding | Echo 传值时注意零值和传空的区别 需要validate require 和 设置指针配合使用 保证不同值的返回不同 不能客户端传0值被判断为空 测试时要空值零值去测试字段是否正确返回 返回错误是否符合预期...

动态规划-子序列问题——1218.最长定差子序列

1.题目解析 题目来源&#xff1a;1218.最长定差子序列——力扣 测试用例 2.算法原理 1.状态表示 本题可以看作是寻找一个等差序列&#xff0c;并且公差给出&#xff0c;这里并不是普通的使用一个dp表&#xff0c;而是将arr与dp表同时存储于一个哈希表&#xff0c;arr[i]映射dp…...

双子塔楼宇可视化系统:提升建筑管理与运营效率

利用图扑可视化技术对双子塔楼宇的各项功能进行实时监控和管理。通过数据分析优化资源配置&#xff0c;提高能源效率&#xff0c;增强楼宇安全性&#xff0c;实现智能化运营。...

32位的ARMlinux的4字节变量原子访问问题

在32位的ARM Linux内核中&#xff0c;4字节整型变量通常被认为是原子操作。 这主要是因为&#xff1a; 对齐要求&#xff1a;在ARM架构中&#xff0c;4字节整型变量通常是按4字节对齐存储的&#xff0c;这样可以确保在读取和写入时&#xff0c;CPU能够以单个指令完成操作。 …...

用哪种建站程序做谷歌SEO更容易?

做网站很容易&#xff0c;但做一个能带来流量和订单的网站就没那么简单了。尤其是在谷歌SEO优化方面&#xff0c;不同的建站程序对SEO的支持程度也不同。在这方面&#xff0c;WordPress和Shopify无疑是最佳选择。 WordPress作为一个内容管理系统&#xff08;CMS&#xff09;&am…...

IPsec简单介绍

VPN相关介绍 VPN&#xff1a;虚拟私有网络 例如&#xff1a;像这种不加密的 PPTPL2TP ------- 一般用在windows server 服务端&#xff08;但是大多数企业不用这个&#xff09; 假如总公司内部的PC1要去访问分公司内部的PC2&#xff08;一般用在公司服务器有内网的服务&#…...

颠覆级AI:10秒生成超清视频

颠覆级AI&#xff1a;10秒生成超清视频 Pyramid-Flow 是一款开源 AI 视频生成神器&#x1f4bb;&#xff0c;只需文字或图片即可极速生成高清视频&#x1f3a5;&#xff01;高效、高清、资源需求低&#xff0c;适合创作广告、教学视频等多种用途&#x1f680;&#xff0c;快来…...

《西安科技大学学报》

《西安科技大学学报》主要刊载安全科学与工程、矿业工程、建筑与土木工程、地质与环境工程、测绘工程、材料科学与工程、化学与化工、机械工程、电气工程及自动化、通信与信息工程、计算机科学与工程、矿业经济管理等专业领域内具有创新性的学术论文和科研成果。 来稿必须符合以…...

redis详细教程(2.List教程)

List是一种可以存储多个有序字符串的数据类型&#xff0c;其中的元素按照顺序排列&#xff08;可以重复出现&#xff09;&#xff0c;可以通过数字索引来访问列表中的元素&#xff0c;索引可以从左到右或者从右到左。 Redis 列表可以通过两种方式实现&#xff1a;压缩列表&…...

电子电气架构 --- 电气系统工程

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无利益不试图说服别人,是精神上的节…...

15-4连续子串和的整除问题

问题描述 小M是一个五年级的小学生&#xff0c;今天他学习了整除的知识&#xff0c;想通过一些练习来巩固自己的理解。他写下了一个长度为 n 的正整数序列 a_0, a_1, ..., a_{n-1}&#xff0c;然后想知道有多少个连续子序列的和能够被一个给定的正整数 b 整除。你能帮小M解决这…...

Spring源码:Bean创建、Bean获取

Bean是怎么被创建&#xff0c;如何获取Bean&#xff0c;基于Spring 5.3.24版本&#xff0c;Spring Boot 可用 2.7.6 结论&#xff1a; 创建&#xff1a;非懒加载的单实例bean在容器创建的时候创建&#xff0c;通过beanFactory的doGetBean方法&#xff0c;利用反射进行创建&…...

MetaArena推出《Final Glory》:引领Web3游戏技术新风向

随着区块链技术的日益成熟&#xff0c;Web3游戏成为了游戏产业探索的新方向&#xff0c;将去中心化经济与虚拟世界结合在一起&#xff0c;形成了一个全新的生态体系。然而&#xff0c;尽管Web3游戏展示了令人兴奋的可能性&#xff0c;但其背后的技术障碍依旧严峻&#xff0c;特…...

玩转Shodan:深度挖掘特定漏洞与脆弱资产的实战技巧

内容预览 ≧∀≦ゞ Shodan进阶使用之发现并解锁隐藏的脆弱资产声明导语VNC未授权访问查询被黑的网站查询思科未授权设备查询MongoDB未授权访问搜索后台管理页面结语 Shodan进阶使用之发现并解锁隐藏的脆弱资产 声明 笔记内容参考了B站UP主泷羽sec的学习视频&#xff0c;如有侵…...

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选择判断结构详解:逻辑分支与条件判断

目录 &#x1f354; if选择判断结构作用 1.1 if选择判断结构的基本语法 1.2 if选择结构案例 1.3 if...else...结构 1.4 if...elif...else多条件判断结构 1.5 if嵌套结构 &#x1f354; 综合案例&#xff1a;石头剪刀布 2.1 需求分析 2.2 代码实现 2.3 随机出拳 &…...

邮件系统SSL加密传输,保护你的电子邮件免受网络威胁

在互联网的浪潮中&#xff0c;企业数字化转型的步伐不断加快。企业邮箱作为数字化应用的重要组成部分&#xff0c;已成为员工沟通、协同工作和企业管理的关键工具。但是在公共网络安全性普遍较弱的背景下&#xff0c;黑客容易侵入企业网络&#xff0c;监控流量&#xff0c;截获…...

Redis_写时复制(cow)

Redis会根据配置&#xff0c;每隔一段时间中对Redis服务中当下的数据集进行快照。配置自动生成rdb文件&#xff0c;后台使用的是bgsave方式。 save 60 1000 //关闭RDB只需要将所有的save保存策略注释掉即可Redis借助操作系统提供的写时复制技术&#xff08;Copy-On-Write, COW…...

【mysql进阶】4-5. InnoDB 内存结构

InnoDB 内存结构 1 InnoDB存储引擎中内存结构的主要组成部分有哪些&#xff1f; &#x1f50d; 分析过程 从官⽹给出的InnoDB架构图中可以找到答案 InnoDB存储引擎架构链接&#xff1a;https://dev.mysql.com/doc/refman/8.0/en/innodb-architecture.html ✅ 解答问题 InnoD…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...