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

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[i1][0],dp[i1][1])+a[i]
对于a[i] == a[i-1]+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]
  2. 若此时不选择a[i],那么当然得选择a[i-1]才会更好。故dp[i][0]=dp[i−1][1]dp[i][0]=dp[i-1][1]dp[i][0]=dp[i1][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[i1][0]dp[i][1]=dp[i1][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 思路 因为跟序列的下标无关&#xff0c;所以先对数组a排个序。那么每次选择只会影响两侧的元素。 记号 令dp[i]dp[i]dp[i]表示排序后a[1..i]a[1..i]a[1..i]能够获得的最大点数。 但是这样不足以区分是否当前元素可以被使用&#xff0c;所…...

geoserver之BlobStores使用

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

跨域问题以及Ajax和Axios的区别

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

现代卷积神经网络(AlexNet)

专栏&#xff1a;神经网络复现目录 本章介绍的是现代神经网络的结构和复现&#xff0c;包括深度卷积神经网络&#xff08;AlexNet&#xff09;&#xff0c;VGG&#xff0c;NiN&#xff0c;GoogleNet&#xff0c;残差网络&#xff08;ResNet&#xff09;&#xff0c;稠密连接网络…...

单向非循环链表

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

Vue2的基本内容(一)

目录 一、插值语法 二、数据绑定 1.单向数据绑定 2.双向数据绑定 三、事件处理 1.绑定监听 2.事件修饰符 四、计算属性computed和监视属性watch 1.计算属性-computed 2.监视属性-watch &#xff08;1&#xff09;通过 watch 监听 msg 数据的变化 &#xff08;2&a…...

蚁群算法优化最优值

%%%%%%%%%%%%%%蚁群算法求函数极值%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%% clear all; %清除所有变量 close all; %清图 clc; %清屏 m 20; %蚂蚁个数 G 500; %最大迭代次数 Rho 0.9; %信息素蒸发系数 P0 0.2; %转移概率常数 XMAX 5; %搜索变量 x…...

Docker镜像的内部机制

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

每日的时间安排规划

14:23 2023年3月4日星期六 开始 现在我要做一套试卷。模拟6级考试。 现在是&#xff1a; 16:22 2023年3月4日星期六。 做完了线上的试卷&#xff01; 发现我真的是不太聪明的样子&#xff01; 明明买的有历年真题&#xff0c;做真题就行了&#xff0c;还要做它们出的模拟的…...

【C++】类和对象——六大默认成员函数

&#x1f3d6;️作者&#xff1a;malloc不出对象 ⛺专栏&#xff1a;C的学习之路 &#x1f466;个人简介&#xff1a;一名双非本科院校大二在读的科班编程菜鸟&#xff0c;努力编程只为赶上各位大佬的步伐&#x1f648;&#x1f648; 目录前言一、类的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)

目录 题目&#xff1a;剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣&#xff08;Leetcode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;剑指 Offer 32 - III. 从上到下打…...

【刷题笔记】之二分查找(搜索插入位置。在排序数组中查找元素的第一个和最后一个位置、x的平方根、有效的完全平方数)

1. 二分查找题目链接 704. 二分查找 - 力扣&#xff08;LeetCode&#xff09;给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -…...

一起Talk Android吧(第五百一十五回:绘制向外扩散的水波纹)

文章目录整体思路实现方法示例代码各位看官们大家好&#xff0c;上一回中咱们说的例子是"Java中的进制转换",这一回中咱们说的例子是"绘制向外扩散的水波纹"。闲话休提&#xff0c;言归正转&#xff0c; 让我们一起Talk Android吧&#xff01; 整体思路 …...

基于粒子群改进的支持向量机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.计算机程序创始人&#xff1a;勒芙蕾丝伯爵夫人2.首位获得图灵奖的女性&#xff1a;法兰艾伦3.谷歌经典首页守护神&#xff1a;玛丽莎梅耶尔4.COBOL之母&#xff1a;葛丽丝穆雷霍普5.史上最强游戏程序媛-余国荔说起程序员的话&#xff0c;人们想到的都会是哪些理工科…...

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 、…...

业务系统对接大模型的基础方案:架构设计与关键步骤

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

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

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

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;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&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

tree 树组件大数据卡顿问题优化

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