美文网首页
[CodeForce455A]

[CodeForce455A]

作者: 影踪派熊猫人武僧 | 来源:发表于2018-12-22 17:01 被阅读0次

    题面描述

    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.
    给定一个由n个整数组成的序列。玩家可以做几个步骤。在单个步骤中,他可以选择序列的元素(假设为a_k)并删除它,此时,所有等于a_k+1和a_k-1的元素也必须从序列中删除。这个步骤给玩家带来a_k点数。

    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).
    第一行包含一个整数n(1≤n≤105),表示Alex序列中有多少个数字。
    第二行包含n个整数a1,a2,…,an(1≤105)

    输出格式

    输出一个整数——Alex可以获得的最大点数

    样例

    样例输入

    9
    1 2 1 3 2 2 2 2 3

    样例输出

    10

    题解

    先求出数列中每一个数字k的出现次数num[k]
    考虑取任意一个数x时只会影响到x+1x-1,我们可以先设dp[i]表示选取num后可以取得的最大值。因为任意取两个数a和b,若选取a后可以选取b,则选取b后可以选取a,因此我们只考虑x与x-1之间的关系。这样我们就很容易得到递推式:
    dp[i]=\begin{cases} 0 && i=0\\ num[1]*1 && i=1\\ max(dp[i-1],dp[i-2]+num[i]*i) && else \end{cases}
    注意,最后一重for循环要从2循环至已知的maxn

    #include<bits/stdc++.h>
    #define maxn 1000050
    using namespace std;
    inline char get(){
        static char buf[3000],*p1=buf,*p2=buf;
        return p1==p2 && (p2=(p1=buf)+fread(buf,1,3000,stdin),p1==p2)?EOF:*p1++;
    }
    inline long long read(){
        register char c=getchar();register long long f=1,_=0;
        while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();
        while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();
        return _*f;
    }
    long long note,n,a[maxn],dp[maxn];
    long long op=0;
    int main(){
        //freopen("1.txt","r",stdin);
        n=read();
        for(register long long i=1;i<=n;i++)a[i]=read(),dp[a[i]]+=a[i],note=max(note,a[i]);
        for(register long long i=2;i<=note;i++)dp[i]=max(dp[(i)-1],dp[(i)-2]+dp[i]),op=max(dp[i],op);
        cout<<op<<endl;
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:[CodeForce455A]

          本文链接:https://www.haomeiwen.com/subject/ckoikqtx.html