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

区间价值 --- 题解--动态规划

目录

区间价值

题目描述

输入描述:

输出描述:

输入

输出

备注:

思路:

代码:


 

区间价值

J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com)
 

时间限制:C/C++ 2秒,其他语言4秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

对于一个数组a,定义其价值是其中不同的数的个数,比如对于数组[3,2,2,3,1],价值就是3。对于一个给定的长度len,求出所有长度为lenlenlen的子区间的价值之和是对于吉吉国王来说很重要,现在吉吉国王会告诉你他想知道的长度lenlenlen,你需要告诉吉吉国王答案。

比如数组[3,2,2,3,1],长度为2的子区间有[3,2],[2,2],[2,3],[3,1],那么价值分别是2,1,2,2,因此这个数组长度为2的价值和就是7。

输入描述:

第一行一个n表示数组的长度。

第二行n个数,第iii个数表示ai。

第三行一个q表示询问的次数。

接下来q行,每行一个整数表示查询的长度。

输出描述:

输出q行,第i行表示第i个询问的答案。

示例1

输入

5
3 2 4 3 1
4
1
2
3
4

输出

5
8
9
7

备注:

1≤n≤1e6 

思路:

这道题容易想到的是暴力解法(区间dp)但这肯定是会爆时间的。

现在设dp[i] 表示区间为i时的价值和。

那怎么从dp[i-1] 转移到 dp[i]

假如 当前区间为3, 数组为 32441

324 -> 3244 贡献不变

244 -> 2441 贡献加1

441 -> null 贡献-2

这里可以看出从dp[i-1] 到 dp[i] 会损伤掉后面 i-1个数的贡献值,并且前几个区间有s[i]的贡献增加。

前几个区间中那些区间是会提供贡献,或者说那些数在区间变大时可以提供贡献,这是可以预处理出来的,因为可以观察发现只有两个相同数的相隔距离大于等于i时,他们才会在长度为i的区间中提供一个贡献。(这里需要用一个后缀和统计)

代码:

import java.util.Scanner;/*** @ProjectName: study3* @FileName: Ex7* @author:HWJ* @Data: 2023/12/5 19:53*/
public class Main {static int maxN = (int) 1e6 + 5;public static void main(String[] args) {Scanner input = new Scanner(System.in);int n = input.nextInt();int[] arr = new int[maxN];int[] last = new int[maxN];long[] s = new long[maxN];int[] diff = new int[maxN];int[] cnt = new int[maxN];for (int i = 1; i <= n; i++) {arr[i] = input.nextInt();s[i - last[arr[i]]]++;last[arr[i]] = i;}for(int i = n; i > 0; i--){s[i] = s[i] + s[i + 1];}int tot = 0;for(int i = n; i > 0; i--){if (++cnt[arr[i]] == 1) tot++;diff[n - i + 1] = tot;}long[] ans = new long[n + 1];ans[1] = n;for(int i = 2; i <= n; i++){ans[i] = ans[i - 1] + s[i] - diff[i - 1];}int q = input.nextInt();for (int i = 0; i < q; i++) {int a = input.nextInt();System.out.println(ans[a]);}}
}

相关文章:

区间价值 --- 题解--动态规划

目录 区间价值 题目描述 输入描述: 输出描述: 输入 输出 备注: 思路&#xff1a; 代码&#xff1a; 区间价值 J-区间价值_牛客竞赛动态规划专题班习题课 (nowcoder.com) 时间限制&#xff1a;C/C 2秒&#xff0c;其他语言4秒 空间限制&#xff1a;C/C 262144K&…...

计算机毕业设计 基于大数据的心脏病患者数据分析管理系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…...

20:kotlin 类和对象 --泛型(Generics)

类可以有类型参数 class Box<T>(t: T) {var value t }要创建类实例&#xff0c;需提供类型参数 val box: Box<Int> Box<Int>(1)如果类型可以被推断出来&#xff0c;可以省略 val box Box(1)通配符 在JAVA泛型中有通配符?、? extends E、? super E&…...

我对迁移学习的一点理解(系列2)

文章目录 我对迁移学习的一点理解 我对迁移学习的一点理解 源域和目标域是相对的概念&#xff0c;指的是在迁移学习任务中涉及到的两个不同的数据集或领域。 源域&#xff08;Source Domain&#xff09;通常指的是已经进行过训练和学习的数据集&#xff0c;它被用来提取特征、…...

Spring MVC学习随笔-控制器(Controller)开发详解:控制器跳转与作用域(二)视图模板、静态资源访问

学习视频&#xff1a;孙哥说SpringMVC&#xff1a;结合Thymeleaf&#xff0c;重塑你的MVC世界&#xff01;&#xff5c;前所未有的Web开发探索之旅 衔接上文Spring MVC学习随笔-控制器(Controller)开发详解&#xff1a;控制器跳转与作用域&#xff08;一&#xff09; SpingMVC中…...

原型模式(Prototype Pattern)

1 基本概念 1.1 大佬文章 设计模式是什么鬼&#xff08;原型&#xff09; 详解设计模式&#xff1a;原型模式-腾讯云开发者社区-腾讯云 1.2 知识汇总 &#xff08;1&#xff09;原型模式&#xff1a;先 new 一个实例&#xff0c;该实例符合需求&#xff0c;之后再根据这个实…...

IM通信技术快速入门:短轮询、长轮询、SSE、WebSocket

文章目录 1. 引言2. 短轮询&#xff08;Short Polling&#xff09;2.1 原理2.2 代码示例2.2.1 服务器端&#xff08;Node.js&#xff09;2.2.2 客户端&#xff08;HTML JavaScript&#xff09; 3. 长轮询&#xff08;Long Polling&#xff09;3.1 原理3.2 代码示例3.2.1 服务器…...

04_W5500_TCP_Server

上一节我们完成了TCP_Client实验&#xff0c;这节使用W5500作为服务端与TCP客户端进行通信。 目录 1.W5500服务端要做的&#xff1a; 2.代码分析&#xff1a; 3.测试&#xff1a; 1.W5500服务端要做的&#xff1a; 服务端只需要打开socket&#xff0c;然后监听端口即可。 2…...

入门Redis学习总结

记录之前刚学习Redis 的笔记&#xff0c; 主要包括Redis的基本数据结构、Redis 发布订阅机制、Redis 事务、Redis 服务器相关及采用Spring Boot 集成Redis 实现增删改查基本功能 一&#xff1a;常用命令及数据结构 1.Redis 键(key) # 设置key和value 127.0.0.1:6379> set …...

SpringSecurity6 | 自定义登录页面

✅作者简介&#xff1a;大家好&#xff0c;我是Leo&#xff0c;热爱Java后端开发者&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f34e;个人主页&#xff1a;Leo的博客 &#x1f49e;当前专栏&#xff1a; Java从入门到精通 ✨特色专栏&#xf…...

从单向链表中删除指定值的节点

输入一个单向链表和一个节点的值&#xff0c;从单向链表中删除等于该值的节点&#xff0c;删除后如果链表中无节点则返回空指针。 链表的值不能重复。构造过程&#xff0c;例如输入一行数据为:6 2 1 2 3 2 5 1 4 5 7 2 2则第一个参数6表示输入总共6个节点&#xff0c;第二个参数…...

Vue2与Vue3的语法对比

Vue2与Vue3的语法对比 Vue.js是一款流行的JavaScript框架&#xff0c;通过它可以更加轻松地构建Web用户界面。随着Vue.js的不断发展&#xff0c;Vue2的语法已经在很多应用中得到了广泛应用。而Vue3于2020年正式发布&#xff0c;带来了许多新的特性和改进&#xff0c;同时也带来…...

实时动作识别学习笔记

目录 yowo v2 yowof 判断是在干什么,不能获取细节信息 yowo v2 https://github.com/yjh0410/YOWOv2/blob/master/README_CN.md ModelClipmAPFPSweightYOWOv2-Nano1612.640ckptYOWOv2-Tiny...

5G常用简称

名称缩写全称非周期 信道状态信息参考信号aperidoc CSIAperidoc Channel State Information缓冲区状态报告BSRBuffer Status Report小区特定无线网络标识CS-RNTICell-Specific Radio Network Temporary Identifier主小区组MCGMaster Cell groupMCG的节点MNMasternode主小区PCel…...

自动化测试框架性能测试报告模板

一、项目概述 1.1 编写目的 本次测试报告&#xff0c;为自动化测试框架性能测试总结报告。目的在于总结我们课程所压测的目标系统的性能点、优化历史和可优化方向。 1.2 项目背景 我们公开课的性能测试目标系统。主要是用于我们课程自动化测试框架功能的实现&#xff0c;以及…...

【SpringBoot】解析Springboot事件机制,事件发布和监听

解析Springboot事件机制&#xff0c;事件发布和监听 一、Spring的事件是什么二、使用步骤2.1 依赖处理2.2 定义事件实体类2.3 定义事件监听类2.4 事件发布 三、异步调用3.1 启用异步调用3.2 监听器方法上添加 Async 注解 一、Spring的事件是什么 Spring的事件监听&#xff08;…...

华为ensp实验——基于全局地址池的DHCP组网实验

目录 前言实验目的实验内容实验结果 前言 该实验基于华为ensp&#xff0c;版本号是1.3.00.100 V100R003C00SPC100&#xff0c;只供学习和参考&#xff0c;不作任何商业用途。 具体的DHCP命令可以看系列文章链接&#xff0c;计算机网络实验&#xff08;华为eNSP模拟器&#xff…...

如何选择一款安全可靠的跨网安全数据交换系统?

随着网络和数据安全的重视程度增加&#xff0c;为了有效地保护内部的核心数据资产&#xff0c;普遍会采用内外网隔离的策略。像国内的政府机构、金融、能源电力、航空航天、医院等关乎国计民生的行业和领域均已进行了网络的隔离&#xff0c;将内部划分成不同的网段&#xff0c;…...

基于c++版本的数据结构改-python栈和队列思维总结

##栈部分-&#xff08;叠猫猫&#xff09; ##抽象数据类型栈的定义&#xff1a;是一种遵循先入后出的逻辑的线性数据结构。 换种方式去理解这种数据结构如果我们在一摞盘子中取到下面的盘子&#xff0c;我们首先要把最上面的盘子依次拿走&#xff0c;才可以继续拿下面的盘子&…...

算法通关村第七关—迭代实现二叉树的遍历(黄金)

迭代实现二叉树的遍历 迭代法实现前序遍历 前序遍历是中左右&#xff0c;如果还有左子树就一直向下找。完了之后再返回从最底层逐步向上向右找。不难写出如下代码&#xff1a;&#xff08;注意代码中&#xff0c;空节点不入栈&#xff09; public List<Integer>preorde…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...