CodeForce 455A. Boredom
题目链接
CodeForce 455A. Boredom
思路
因为跟序列的下标无关,所以先对数组a排个序。那么每次选择只会影响两侧的元素。
记号
令dp[i]dp[i]dp[i]表示排序后a[1..i]a[1..i]a[1..i]能够获得的最大点数。
但是这样不足以区分是否当前元素可以被使用,所以再开一个维度,
令:
dp[i][0]dp[i][0]dp[i][0]表示我们无法使用当前元素a[i]a[i]a[i]所获得的最大点数。
dp[i][1]dp[i][1]dp[i][1]表示我们使用当前元素a[i]a[i]a[i]能够获得的最大点数。
那么对相邻的两个元素讨论即可。
状态转移方程
对于a[i] > a[i-1] + 1
,
那么当前选择不会影响到之前的点数。所以
dp[i][1]=max(dp[i−1][0],dp[i−1][1])+a[i]dp[i][1] = max(dp[i-1][0],dp[i-1][1]) + a[i]dp[i][1]=max(dp[i−1][0],dp[i−1][1])+a[i]
对于a[i] == a[i-1]+1
,
- 若此时选择a[i],则与a[i-1]相等的都不能被选中。j是最大满足a[j] < a[i-1]的下标j,那么dp[i][1]=dp[j]+a[i]dp[i][1] = dp[j] + a[i]dp[i][1]=dp[j]+a[i]
- 若此时不选择a[i],那么当然得选择a[i-1]才会更好。故dp[i][0]=dp[i−1][1]dp[i][0]=dp[i-1][1]dp[i][0]=dp[i−1][1]
对于a[i] == a[i-1],那么当a[i-1]不能被选择时,a[i]也不能被选择。反之亦然。
故有dp[i][0]=dp[i−1][0]dp[i][1]=dp[i−1][1]+a[i]dp[i][0]=dp[i-1][0] \\dp[i][1] = dp[i-1][1] + a[i] dp[i][0]=dp[i−1][0]dp[i][1]=dp[i−1][1]+a[i]
代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;
vector<LL> a;int main() {int n;cin >> n;a.resize(n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i];}sort(a.begin() + 1, a.end());vector<vector<LL>> dp(n + 1, vector<LL>(2));dp[1][1] = a[1];for (int i = 2; i <= n; ++i) {if (a[i] > a[i - 1] + 1) {// dp[i][1]表示使用了当前元素dp[i][1] = max(dp[i - 1][0], dp[i - 1][1]) + a[i];} else {if (a[i] == a[i - 1] + 1) {// the prev of first element equal to a[i-1]int j = lower_bound(a.begin() + 1, a.begin() + i, a[i - 1]) - a.begin() - 1;dp[i][1] = max(dp[j][1], dp[j][0]) + a[i];dp[i][0] = dp[i - 1][1];} else if (a[i] == a[i - 1]) {dp[i][0] = dp[i - 1][0];dp[i][1] = dp[i - 1][1] + a[i];}}
// printf("dp[%d]=%d\n", i, max(dp[i][0], dp[i][1]));}cout << max(dp[n][0], dp[n][1]);
}
相关文章:
CodeForce 455A. Boredom
题目链接 CodeForce 455A. Boredom 思路 因为跟序列的下标无关,所以先对数组a排个序。那么每次选择只会影响两侧的元素。 记号 令dp[i]dp[i]dp[i]表示排序后a[1..i]a[1..i]a[1..i]能够获得的最大点数。 但是这样不足以区分是否当前元素可以被使用,所…...

geoserver之BlobStores使用
概述 geoserver是常用的地图服务器之一,除了基本的能力之外,也提供了很多的插件方便大家使用。在本文,讲述一下如何在geoserver中使用BlobStores和gwc-sqlite-plugin插件实现地图的切片和部署。 BlobStores简介 在geoserver中,…...

跨域问题以及Ajax和Axios的区别
文章目录1. 同源策略2. 同源策略案例3. 什么是跨域4. 跨域解决方法4.1 Ajax的jsonp4.2 CORS方式4.3 Nginx 反向代理5. Axios 和 Ajax 的区别6. Axios 和 Ajax 的区别及优缺点6.1 Ajax:6.1.1 什么是Ajax6.1.2 Ajax的原理6.1.3 核心对象6.1.4 Ajax优缺点6.1.4.1 优点&…...

现代卷积神经网络(AlexNet)
专栏:神经网络复现目录 本章介绍的是现代神经网络的结构和复现,包括深度卷积神经网络(AlexNet),VGG,NiN,GoogleNet,残差网络(ResNet),稠密连接网络…...

单向非循环链表
1、顺序表遗留问题 1. 中间/头部的插入删除,时间复杂度为O(N) 2. 增容需要申请新空间,使用malloc、realloc等函数拷贝数据,释放旧空间。会有不小的消耗。 3. 当我们以2倍速度增容时,势必会有一定的空间浪费。例如当前容量为100&a…...

Vue2的基本内容(一)
目录 一、插值语法 二、数据绑定 1.单向数据绑定 2.双向数据绑定 三、事件处理 1.绑定监听 2.事件修饰符 四、计算属性computed和监视属性watch 1.计算属性-computed 2.监视属性-watch (1)通过 watch 监听 msg 数据的变化 (2&a…...
蚁群算法优化最优值
%%%%%%%%%%%%%%蚁群算法求函数极值%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%% clear all; %清除所有变量 close all; %清图 clc; %清屏 m 20; %蚂蚁个数 G 500; %最大迭代次数 Rho 0.9; %信息素蒸发系数 P0 0.2; %转移概率常数 XMAX 5; %搜索变量 x…...

Docker镜像的内部机制
Docker镜像的内部机制 镜像就是一个打包文件,里面包含了应用程序还有它运行所依赖的环境,例如文件系统、环境变量、配置参数等等。 环境变量、配置参数这些东西还是比较简单的,随便用一个 manifest 清单就可以管理,真正麻烦的是文…...

每日的时间安排规划
14:23 2023年3月4日星期六 开始 现在我要做一套试卷。模拟6级考试。 现在是: 16:22 2023年3月4日星期六。 做完了线上的试卷! 发现我真的是不太聪明的样子! 明明买的有历年真题,做真题就行了,还要做它们出的模拟的…...

【C++】类和对象——六大默认成员函数
🏖️作者:malloc不出对象 ⛺专栏:C的学习之路 👦个人简介:一名双非本科院校大二在读的科班编程菜鸟,努力编程只为赶上各位大佬的步伐🙈🙈 目录前言一、类的6个默认成员函数二、构造…...
远程debug被arthas watch了的idea
开发工具idea端(2021.2.1) 远程调试 被 应用了 修改的arthas端 的 鸡idea端(2022.3.2) A. 鸡idea端 鸡idea: “D:\IntelliJ IDEA 2022.3.2\bin\idea64.exe” 中安装有目标插件 比如 RedisNew-2022.07.24.zip 对文件 “D:\IntelliJ IDEA 2022.3.2\bin\idea64.exe.vmoptions” 新…...

Cesium实现的光柱效果
Cesium实现的光柱效果 效果展示: 可以通过拼接两个entity来实现这个效果: 全部代码; index.html <!DOCTYPE html> <html><head><meta charset...
你最爱记混的slice()和splice()
slice()方法:选取数组的一部分,并返回一个新数组 该方法不会改变原始数组,而是将截取到的元素封装到一个新数组中返回 语法:array.slice(start,end),参数的介绍如下: 语法:array.slice(start,end),参数的介绍如下: 1.start:截取开始的位置的索引,包含开始索引 2.…...

【LeetCode】剑指 Offer(15)
目录 题目:剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 32 - III. 从上到下打…...

【刷题笔记】之二分查找(搜索插入位置。在排序数组中查找元素的第一个和最后一个位置、x的平方根、有效的完全平方数)
1. 二分查找题目链接 704. 二分查找 - 力扣(LeetCode)给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -…...
一起Talk Android吧(第五百一十五回:绘制向外扩散的水波纹)
文章目录整体思路实现方法示例代码各位看官们大家好,上一回中咱们说的例子是"Java中的进制转换",这一回中咱们说的例子是"绘制向外扩散的水波纹"。闲话休提,言归正转, 让我们一起Talk Android吧! 整体思路 …...

基于粒子群改进的支持向量机SVM的情感分类识别,pso-svm情感分类识别
目录 支持向量机SVM的详细原理 SVM的定义 SVM理论 Libsvm工具箱详解 简介 参数说明 易错及常见问题 SVM应用实例,基于SVM的情感分类预测 代码 结果分析 展望 支持向量机SVM的详细原理 SVM的定义 支持向量机(support vector machines, SVM)是一种二分类模型,它的基本模型…...

【python中的列表和元组】
文章目录前言一、列表及其使用1.列表的特点2. 列表的使用方法二、元组及其特点1.元组的类型是tuple1.元组的查找操作2. 计算元组某个元素出现的次数3.统计元组内元素的个数总结前言 本文着重介绍python中的列表和元组以及列表和元组之间的区别 一、列表及其使用 1.列表的特点…...

世界顶级五大女程序媛,不仅技术强还都是美女
文章目录1.计算机程序创始人:勒芙蕾丝伯爵夫人2.首位获得图灵奖的女性:法兰艾伦3.谷歌经典首页守护神:玛丽莎梅耶尔4.COBOL之母:葛丽丝穆雷霍普5.史上最强游戏程序媛-余国荔说起程序员的话,人们想到的都会是哪些理工科…...

Linux- 系统随你玩之--文件管理-双生姐妹花
文章目录1、前言2、文件管理-双生姐妹花2.1、 df2.1.1、 df 语法2.1.1 、常用参数2.2、 du2.2.1、du 语法2.1.1、 常用参数2.3、双生姐妹花区别2.3.1、 查看文件统计 的计算方式不同2.3.2 、删除文件情况下统计结果 不同2.3.3 、针对双生姐妹花区别 结语3、双生姐妹花实操3.1 、…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

【WiFi帧结构】
文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成:MAC头部frame bodyFCS,其中MAC是固定格式的,frame body是可变长度。 MAC头部有frame control,duration,address1,address2,addre…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...

04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...