• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Codeforces456C-Boredom(简单DP)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

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.

Input

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).

Output

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

Examples
input
2
1 2
output
2
input
3
1 2 3
output
4
input
9
1 2 1 3 2 2 2 2 3
output
10
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.

 题意:

  每次从n个数中选中数值为Ak将其删去,并将值为Ak-1的数和值为Ak+1的数全部删去,得到Ak的分数。问最大可获得的分数。

题解:

  DP一下就好了。

 

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
long long cnt[maxn],dp[maxn];
int main()
{
    int n;
    while(cin>>n)
    {
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;i++)
        {
            int x;
            cin>>x;
            cnt[x]++;
        }
        dp[0]=0,dp[1]=cnt[1];
        long long ans=0;
        for(int i=2;i<maxn;i++)
        {
            dp[i]=max(dp[i-1],dp[i-2]+cnt[i]*i);
            ans=max(ans,dp[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

 

 

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C#实现QQ接口软件--QQ的HTTP接口协议探究发布时间:2022-07-13
下一篇:
10在C#中读取文件发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap