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

力扣每日一题(+日常水题|树型dp)

740. 删除并获得点数 - 力扣(LeetCode)

简单分析一下:

每一个数字其实只有2个状态选 or 不

可得预处理每一个数初始状态(不选为0,选为所有x的个数 * x)累加即可

for(auto &x : nums)dp[x][1] += x;

每选一个树 i 删去 i + 1 和 i - 1

故我们可以将 i - 1视为 i 的父节点, i + 1视为 i 的子节点(此时思路就向树形dp经典题"参加舞会"一样如果i节点参与,其子节点和父节点不参与)

可得

 for(int i = 2; i <= n;i++){dp[i][1] += dp[i - 1][0];dp[i][0] += dp[i - 1][1];}

再考虑特殊情况:中间断层 1 5 or 任意不连续数字串 

此时对与5 显然 其没有父节点 和 子节点(无法正常转移)

那么倒退4,我们构建4节点,因为其本身不存在选和不选都不影响最终结果

可得

            if(!dp[i][1]){dp[i][1] = dp[i][0] = mx;continue;}

由于每一个节点的权值大小不同,对于第i个节点为true的时候有特殊情况(即选的权值不如不选的情况)

可得

                dp[i][1] = max(dp[i][1] + dp[i - 1][0], dp[i - 1][1]);dp[i][0] += dp[i - 1][1];

 

由于题目数据范围为

 

故进行转移时只用转移1e4次即可 

//using i64 = int64_t;
class Solution {
public:const int maxn = 1e4 + 10;int dp[10010][2];int deleteAndEarn(vector<int>& nums) {//视为树形dp(easy版)//例如:样例一 == >> 2 3 4//样例二 == >> 4 9 4    memset(dp, 0, sizeof dp);for(auto &x : nums)dp[x][1] += x;int mx = 0;for(int i = 1; i <= 10000; i++){if(!dp[i][1]){dp[i][1] = dp[i][0] = mx;continue;}else{dp[i][1] = max(dp[i][1] + dp[i - 1][0], dp[i - 1][1]);dp[i][0] += dp[i - 1][1];}mx = max({mx,dp[i][1],dp[i][0]});}return max(dp[10000][1], dp[10000][0]);}
};

 时间复杂度:常数级

2251. 花期内花的数目 - 力扣(LeetCode)

  

相关文章:

力扣每日一题(+日常水题|树型dp)

740. 删除并获得点数 - 力扣&#xff08;LeetCode&#xff09; 简单分析一下: 每一个数字其实只有2个状态选 or 不 可得预处理每一个数初始状态(不选为0,选为所有x的个数 * x)累加即可 for(auto &x : nums)dp[x][1] x;每选一个树 i 删去 i 1 和 i - 1 故我们可以将 i…...

使用perming加速训练可预测的模型

监督学习模型的训练流程 perming是一个主要在支持CUDA加速的Windows操作系统上架构的机器学习算法&#xff0c;基于感知机模型来解决分布在欧式空间中线性不可分数据集的解决方案&#xff0c;是基于PyTorch中预定义的可调用函数&#xff0c;设计的一个面向大规模结构化数据集的…...

【数据库】存储引擎InnoDB、MyISAM、关系型数据库和非关系型数据库、如何执行一条SQL等重点知识汇总

目录 存储引擎InnoDB、MyISAM的适用场景 关系型和非关系型数据库的区别 MySQL如何执行一条SQL的 存储引擎InnoDB、MyISAM的适用场景 InnoDB 是 MySQL 默认的事务型存储引擎&#xff0c;只有在需要它不支持的特性时&#xff0c;才考虑使用其它存储引擎。实现了四个标准的隔…...

车道线分割检测

利用opencv&#xff0c;使用边缘检测、全局变化梯度阈值过滤、算子角度过滤、HLS阈值过滤的方法进行车道线分割检测&#xff0c;综合多种阈值过滤进行检测提高检测精度。 1.利用cv2.Sobel()计算图像梯度(边缘检测) import cv2 import numpy as np import matplotlib.pyplot a…...

树莓集团又一力作,打造天府蜂巢成都直播产业园样板工程

树莓集团再次推出惊艳之作&#xff0c;以打造成都天府蜂巢直播产业园为目标。该基地将充分展现成都直播产业园的巨大潜力与无限魅力&#xff0c;成为一个真正的产业园样板工程。 强强联手 打造未来 成都天府蜂巢直播产业园位于成都科学城兴隆湖高新技术服务产业园内&#xff0…...

ubuntu 软件包管理之二制作升级包

Deb 包(Debian 软件包)是一种用于在 Debian 及其衍生发行版(例如 Ubuntu)中分发和安装软件的标准包装格式。它们构成了 Debian Linux 发行版中的软件包管理系统的核心组成部分,旨在简化软件的分发、安装、更新和卸载流程。在本篇文章中,我们将深入探讨以下内容: Deb 包基…...

TCP/IP网络江湖——数据链路层的防御招式(数据链路层下篇:数据链路层的安全问题)

目录 引言 一、 数据链路层的隐私与保密 二、数据链路层的安全协议与加密...

ios项目安装hermes-engine太慢问题

问题说明 ios工程&#xff0c;在使用"pod install"安装依赖的时候&#xff0c;由于超时总是报错 $ pod install ... Installing hermes-engine (0.71.11)[!] Error installing hermes-engine [!] /usr/bin/curl -f -L -o /var/folders/4c/slcchpy55s53ysmz_1_q_gzw…...

构建个人云存储:本地电脑搭建SFTP服务器,开启公网访问,轻松共享与管理个人文件!

本地电脑搭建SFTP服务器&#xff0c;并实现公网访问 文章目录 本地电脑搭建SFTP服务器&#xff0c;并实现公网访问1. 搭建SFTP服务器1.1 下载 freesshd 服务器软件1.3 启动SFTP服务1.4 添加用户1.5 保存所有配置 2. 安装SFTP客户端FileZilla测试2.1 配置一个本地SFTP站点2.2 内…...

springboot 下载文件为excel数据,中文自定义单元格宽度

/**2 * Description:表格自适应宽度(中文支持)3 * Author: 4 * param sheet sheet5 * param columnLength 列数6 */7 private static void setSizeColumn(HSSFSheet sheet, int columnLength) {8 for (int columnNum 0; columnNum < …...

机器学习 面试/笔试题

1. 生成模型 VS 判别模型 生成模型&#xff1a; 由数据学得联合概率分布函数 P ( X , Y ) P(X,Y) P(X,Y),求出条件概率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X)的预测模型。 朴素贝叶斯、隐马尔可夫模型、高斯混合模型、文档主题生成模型&#xff08;LDA&#xff09;、限制玻尔兹曼机…...

某企查ymg_ssr列表详情

js篇— 今天来看下某企查的列表详情–侵删 header发现这个参数 先断点一下 然后上一步 就到了这个地方 就开始扣一下这个js 三大段&#xff0c;先不解混淆了&#xff0c; 给a粘贴出来 &#xff0c;去掉自执行 给结果稍微改一下 缺windows&#xff0c;开始补环境 直接上…...

使用YOLOv5的backbone网络识别图像天气 - P9

目录 环境步骤环境设置包引用声明一个全局的设备 数据准备收集数据集信息构建数据集在数据集中读取分类名称划分训练、测试数据集数据集划分批次 模型设计编写维持卷积前后图像大小不变的padding计算函数编写YOLOv5中使用的卷积模块编写YOLOv5中使用的Bottleneck模块编写YOLOv5…...

TikTok海外扩张:亚马逊的新对手崛起

随着社交媒体和电子商务的融合&#xff0c;TikTok正迅速崭露头角&#xff0c;成为亚马逊等传统电商巨头的潜在竞争对手。这一新兴平台的快速发展引发了广泛的关注&#xff0c;特别是在全球范围内。 在这篇文章中&#xff0c;我们将探讨TikTok海外扩张的战略&#xff0c;以及它…...

CSS详细基础(五)选择器的优先级

本节介绍选择器优先级&#xff0c;优先级决定了元素最终展示的样式~ 浏览器是通过判断CSS优先级&#xff0c;来决定到底哪些属性值是与元素最为相关的&#xff0c;从而作用到该元素上。CSS选择器的合理组成规则决定了优先级&#xff0c;我们也常常用选择器优先级来合理控制元素…...

LLM-TAP随笔——有监督微调【深度学习】【PyTorch】【LLM】

文章目录 5、 有监督微调5.1、提示学习&语境学习5.2、高效微调5.3、模型上下文窗口扩展5.4、指令数据构建5.5、开源指令数据集 5、 有监督微调 5.1、提示学习&语境学习 提示学习 完成预测的三个阶段&#xff1a;提示添加、答案搜索、答案映射 提示添加 “[X] 我感到…...

kafka伪集群部署,使用docker环境拷贝模式

线上启动容器的方式是复制容器的运行环境出来&#xff0c;然后进行运行脚本的形式 1&#xff1a;在home/kafka目录下创建如下目录 2&#xff1a;复制kafka1容器内的数据/bitnami/kafka/data&#xff0c;直接放在1992_data里面&#xff0c;同理,复制kafka2容器内的数据/bitnami/…...

工业交换机一般的价格是多少呢?

工业交换机是一种应用于工业领域的网络设备。它的性能和所有安全指标都比一般商业交换机更加稳定。所以&#xff0c;工业级交换机的价格相对于普通的交换机要稍稍昂贵一些。工业交换机一般的价格是多少呢&#xff1f;每个厂家的交换机价格是不是都一样呢&#xff1f; 首先&…...

QT使用前的知识

QT使用前的知识 常用的快捷键 源文件的内容解释 .pro文件的解释 头文件的解释 构建新的对象—组成对象树 槽函数 自定的信号和槽 槽函数的信号是一个重载函数时 电机按钮触发信号 调用无参数的信号 断开信号...

Unity制作旋转光束

Unity制作旋转光束 大家好&#xff0c;我是阿赵。 这是一个在很多游戏里面可能都看到过的效果&#xff0c;在传送门、魔法阵、角色等脚底下往上散发出一束拉丝形状的光&#xff0c;然后在不停的旋转。 这次来在Unity引擎里面做一下这种效果。 一、准备材料 需要准备的素材很简…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

结构化文件管理实战:实现目录自动创建与归类

手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题&#xff0c;进而引发后续程序异常。使用工具进行标准化操作&#xff0c;能有效降低出错概率。 需要快速整理大量文件的技术用户而言&#xff0c;这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB&#xff0c;…...

Qt/C++学习系列之列表使用记录

Qt/C学习系列之列表使用记录 前言列表的初始化界面初始化设置名称获取简单设置 单元格存储总结 前言 列表的使用主要基于QTableWidget控件&#xff0c;同步使用QTableWidgetItem进行单元格的设置&#xff0c;最后可以使用QAxObject进行单元格的数据读出将数据进行存储。接下来…...

【Elasticsearch基础】Elasticsearch批量操作(Bulk API)深度解析与实践指南

目录 1 Bulk API概述 1.1 什么是批量操作 1.2 Bulk API的优势 2 Bulk API的工作原理 2.1 请求处理流程 2.2 底层机制 3 Bulk API的使用方法 3.1 基本请求格式 3.2 操作类型示例 3.3 响应格式 4 Bulk API的最佳实践 4.1 批量大小优化 4.2 错误处理策略 4.3 性能调…...

【芯片仿真中的X值:隐藏的陷阱与应对之道】

在芯片设计的世界里&#xff0c;X值&#xff08;不定态&#xff09;就像一个潜伏的幽灵。它可能让仿真测试顺利通过&#xff0c;却在芯片流片后引发灾难性后果。本文将揭开X值的本质&#xff0c;探讨其危害&#xff0c;并分享高效调试与预防的实战经验。    一、X值的本质与致…...

unipp---HarmonyOS 应用开发实战

HarmonyOS 应用开发实战指南 1. 开篇&#xff1a;为什么选择 HarmonyOS&#xff1f; 最近在开发鸿蒙应用时&#xff0c;发现很多开发者都在问&#xff1a;为什么要选择 HarmonyOS&#xff1f;这里分享一下我的看法&#xff1a; 生态优势 华为手机用户基数大&#xff0c;市场潜…...

Java编程之组合模式

引言 在软件开发的世界里&#xff0c;我们经常会遇到需要表示"部分-整体"层次结构的场景。比如文件系统中的文件和文件夹、图形界面中的各种组件、企业组织架构中的部门和员工等。这些场景都有一个共同的特点&#xff1a;我们需要以一种统一的方式来处理单个对象和由…...