「CF455A」Boredom
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.
|
1 2 |
2 1 2 |
|
1 |
2 |
|
1 2 |
3 1 2 3 |
|
1 |
4 |
|
1 2 |
9 1 2 1 3 2 2 2 2 3 |
|
1 |
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.
题解
直接dp
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#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])); } |
OI 课件=>
