cf455A Boredom
1 second
256 megabytes
standard input
standard output
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.
low爆了……做div1洋洋得意的5分钟做了A……结果hacked……最后只有重交了A然后rating哗哗的掉
题意是一个序列做删数游戏,如果删去一个x,就还要删掉所有大小是(x+1)、(x-1)的数,这样获得的价值是x,求删完整个序列的最大价值
那么显然如果你要删掉一个数x,那么其他所有大小是x的也要删掉。因为只删一个x、其他x不动,这样显然是不优的
用ans[]保存删去所有大小为x的数能获得的价值
然后f[i][0/1]表示1到i、第i个数取/不取的最大价值
f[i][0]不取可以从第(i-1)个取/不取转移而来
f[i][1]取了只能从第(i-1)个不取转移而来
原来我算f 的时候for只到n……但是应该是到max(a[i])就是无脑100000的……然后hacked
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
int n,x;
LL ans[100010];
LL f[100010][2];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
x=read();
ans[x]+=x;
}
for (int i=1;i<=100000;i++)
{
f[i][0]=max(f[i-1][0],f[i-1][1]);
f[i][1]=f[i-1][0]+ans[i];
}
printf("%lld",max(f[100000][0],f[100000][1]));
}
最新文章
- 登陆mysql时出现unknown variable &#39;character_set_client=UTF8&#39; 的错误
- sphinx续4-coreseek的工作原理
- 时间序列数据库选型——本质是列存储,B-tree索引,抑或是搜索引擎中的倒排索引
- easy ui 下拉级联效果 ,下拉框绑定数据select控件
- 单元测试工具之Xunit
- Sync FrameWork 文件同步 (源码)
- (二)JAVA使用POI操作excel
- 他们都没告诉你适配 Android N 需要注意什么
- 解决Spring中singleton的Bean依赖于prototype的Bean的问题
- MUI 列表页面绑定接口数据
- 关于OpenGL和DX学习的取舍
- C语言实验单片机串口发送int型数据
- No matching provisioning profiles found for ";Applications/MyApp.app”问题解决
- Angular02 将数据添加到组件中
- HDU1085 多重背包
- .net core 命令行(仅作记录)
- B+树的Copy-on-Write设计
- android: 使用本地广播
- gitlab ssh clone问题解决
- Shell教程 之运算符
热门文章
- Sed 与 Linux 等价命令代码鉴赏(转)
- python模块学习之random
- UESTC_Sea Base Exploration CDOJ 409
- Android ScrollView用法
- hdu2208之搜索
- CDH 2、Cloudera Manager的安装
- android假设重写onDraw实现一个相似TextView能够显示表情和链接的控件(一)
- oninput,onpropertychange,onchange的使用方法和差别
- 项目总结之SSI (一)
- UVA 1345 Jamie&#39;s Contact Groups