455A. Boredom

dp, 1500, https://codeforces.com/contest/455/problem/A

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 a~k~) and delete it, at that all elements equal to a~k~ + 1 and a~k~ - 1 also must be deleted from the sequence. That step brings a~k~ points to the player.

Alex is a perfectionist, so he decided to get as many points as possible. Help him.

Input

The first line contains integer n (1 ≤ n ≤ 10^5^) that shows how many numbers are in Alex's sequence.

The second line contains n integers a~1~, a~2~, ..., a~n~ (1 ≤ a~i~ ≤ 10^5^).

Output

Print a single integer — the maximum number of points that Alex can earn.

Examples

input

2
1 2

output

input

3
1 2 3

output

input

9
1 2 1 3 2 2 2 2 3

output

Note

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[i][0] 和 dp[i][1]，分别记录不选择和选择当前数时的最大和，从而逐步构建最终的解。

python

# 高景行 24数学科学学院
M = int(1e5)
a = [0] * (M + 1)
n = int(input())
for x in map(int, input().split()): a[x] += 1
dp = [[0, 0] for _ in range(M + 1)]
# dp[i][0] 不选i, dp[i][1] 选i
for i in range(1, M + 1):
    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
    dp[i][1] = dp[i - 1][0] + a[i] * i
print(max(dp[M][0], dp[M][1]))

初始化动态规划表
python
dp = [[0, 0] for _ in range(M + 1)]
# dp[i][0] 不选i, dp[i][1] 选i
dp 是一个二维列表，dp[i][0] 表示不选择数字 i 时的最大和，dp[i][1] 表示选择数字 i 时的最大和。
动态规划状态转移
python
for i in range(1, M + 1):
    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])
    dp[i][1] = dp[i - 1][0] + a[i] * i
dp[i][0] 表示不选择 i 时的最大和，等于前一个数 i-1 的两种状态的最大值。
dp[i][1] 表示选择 i 时的最大和，等于不选择 i-1 的最大和加上 i 的值乘以其出现次数 a[i]。

【王康安，2020年秋】预处理做个桶。状态转移方程：dp[i] = max(dp[i-1], dp[i-2]+cnt[i]*i)。

python

n = int(input())
arr = list(map(int,input().split()))
dp = [0]*(max(arr) + 1)
cnt = [0]*(max(arr) + 1)
for each in arr:    
    cnt[each] += 1

dp[0] = 0
dp[1] = cnt[1]
for i in range( 2, max(arr)+1 ):    
    dp[i] = max( dp[i-1], dp[i-2] + cnt[i]*i )

print(max(dp))

【李思哲，2020年秋】先将相同的数字打包求和，然后在有数的地方从前往后爬，每次只需要考虑是放弃这次还是上一次的数更好即可。这题虽然不难但是确实让我更加明白了动态规划是个怎样的过程。

【李宗远，2020年秋】以前没用过直接爆开一个大数的方法，然后无脑递归的方法......我听说Python是脚本语言之后一直以为这种方法是C++的专利。学到了学到了，真好用233

python

input()
c = [0]*100001
for m in map(int, input().split()):
    c[m] += 1
    
dp = [0]*100001
for i in range(1, 100001):
    dp[i] = max( dp[i-1], dp[i-2] + i* c[i] )

print(max(dp))

python

# ref: http://codeforces.com/blog/entry/13336
# maximize the sum of numbers that we took. Let precalc array cnt.
# cnt[x] — number of integers x in array a. Now we can easily calculate the DP:
# f(i) = max( f(i-1), f(i-2) + cnt[i]*i), 2<=i<=n
# f(1) = cnt[1]
# f(0) = 0
# The answer is f(n). Asymptotics - O(n)

n = int(input())
a = [int(i) for i in input().split()]

max_value = max(a)
#print(max_value)

cnt = (max_value+1)*[0]
for i in range(n):
        cnt[a[i]] += 1

f = (max_value+1)*[0]
f[0] = 0
f[1] = cnt[1]

for i in range(2,max_value+1):
        if f[i-1] > f[i-2] + cnt[i]*i :
                f[i] = f[i-1]
        else:
                f[i] = f[i-2] + cnt[i]*i

print(f[max_value])

Python a, b = b, a +b - Stack Overflow

In a, b = b, a + b, the expressions on the right hand side are evaluated before being assigned to the left hand side.

python

n = input()
s=[0]*100002
for i in map(int, input().split()):
    s[i] += i

a = b = 0
for d in s:
    a,b = max(a,b),a+d

print(max(a,b))

455A. Boredom ​

455A. Boredom