Alex doesn't like boredom. That's why whenever he gets bored, he comes up with games. One long winter evening he came up with a game and decided to play it.
Given a sequence a consisting of n integers. The player can make several steps. In a single step he can choose an element of the sequence (let's denote it ak) and delete it, at that all elements equal to ak + 1 and ak - 1 also must be deleted from the sequence. That step brings ak points to the player.
Alex is a perfectionist, so he decided to get as many points as possible. Help him.
The first line contains integer n (1 ≤ n ≤ 105) that shows how many numbers are in Alex's sequence.
The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 105).
Print a single integer — the maximum number of points that Alex can earn.
2 1 2
2
3 1 2 3
4
9 1 2 1 3 2 2 2 2 3
10
Consider the third test example. At first step we need to choose any element equal to 2. After that step our sequence looks like this[2, 2, 2, 2]. Then we do 4 steps, on each step we choose any element equals to 2. In total we earn 10 points.
题意:
给出 n(1 ~ 10 ^ 5) 个数,后给出这 n 个数,每次取一个数 k,取的同时,k - 1 与 k + 1 也会消失。每次取的数为本次取的分数,最后使求和的结果最大。
思路:
DP。dp [ i ] = MAX { dp [ i - 1 ] , Max { dp [ 1 ] …… dp [ i - 2 ] } + num [ i ] } ,最后输出 dp [ 100000 ] 即为答案。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; ll num[100005]; int main () { int n; scanf("%d", &n); memset(num, 0, sizeof(num)); for (int i = 0; i < n; ++i) { int ans; scanf("%d", &ans); num[ans] += (ll)ans; } ll Max = 0; Max = max(Max, num[1]); for (int i = 3; i <= 100000; ++i) { Max = max(num[i - 2], Max); num[i] = max(num[i] + Max, num[i - 1]); } printf("%I64d\n", num[100000]); return 0; }
相关推荐
Boredom
语言:English 浪费时间,拯救生命。 Bordombutton是一种有趣,简单的方式来探索网页。 每次单击按钮时,我们都会向您展示一个随机的照片,视频,文章或游戏,我们认为您可能喜欢。
摆脱恐惧
COVID-boredom-buster--前端:获取和保存随机活动-带有JS,CSS和html的前端应用程序
无聊模拟器 一个游戏。 在线玩:
==这到底是什么? == 我很无聊,所以我来看看并从网络友好的角度进行更改。 我主要是从Phaser教程开始的,它将从那里继续进行。 =到目前为止,我们得到了什么? =什么都没有== 01道奇游戏== 一个简单的游戏的快速而...
反乏味项目设置npm install编译和热重装以进行开发npm run serve编译并最小化生产npm run build运行单元测试npm run test:unit整理和修复文件npm run lint自定义配置请参阅。
一个简单,无聊的游戏,是作为“ Advertising”德国项目的一部分而创建的。 要进行下载,请在上方再按一下绿色的“下载”按钮
我自己的总结啊 abbreviate 缩写,缩写为academic 纯理论的accelerometer 加速度测量仪accommodate 适应actuate 激励,驱动actuator 执行机构...blend 混合,调和,配料blow (保险丝)烧断boredom 讨厌,无趣brush 电
(中性/nertral、生气/anger、害怕/fear、高兴/joy、悲伤/sadness、厌恶/disgust、无聊/boredom),采样率48kHz(后压缩到16kHz),16bit量化,语料文本的选取遵从语义中性、无情感倾向的原则,且为日常口语化风格,无过多...
在简要介绍了文献中最重要的贡献之后,为了加深这个问题,我们使用以Boredom倾向量表BPS为主要工具从一项调查收集的数据(Farmer&Sundberg,1986),以确定可能的预防形式应在家庭,社会和机构背景下采用,以不...
拯救我的哈哈用户故事: AS A user,I WANT to see gifs and jokes,SO THAT I alleviate my boredom.描述: 从用户选择的类别生成笑话和相关gif的应用程序。 笑话将通过JokeAPI数据库提供,gif将从giphy提供。 GIVEN ...
and other TV programs make you curious about our physical world -- or if you're a student forced to take a physics course -- now you can pursue the subject without the dread of boredom or the fear ...
and other TV programs make you curious about our physical world -- or if you're a student forced to take a physics course -- now you can pursue the subject without the dread of boredom or the fear ...
and other TV programs make you curious about our physical world -- or if you're a student forced to take a physics course -- now you can pursue the subject without the dread of boredom or the fear ...
and other TV programs make you curious about our physical world -- or if you're a student forced to take a physics course -- now you can pursue the subject without the dread of boredom or the fear ...
无聊的项目 一个消除无聊的应用程序! 描述 在一次疯狂的大流行中,您是否会感到无聊!...SO THAT I can escape boredom 验收标准 GIVEN I need to escape my bored reality WHEN I open the website THEN I am present